Nitu the Laziest Girl

Did you hear about the lazy girl Nitu? She loves programming a lot and spends most of her times in problem solving. Her teacher is so pleased with her. In a recent programming contest she achieved a very good position. Her teacher believes that one day she will become a legendary grandmaster. But there is only one problem. She is so lazy and also known as the world laziest girl.

Today her teacher is very angry with her. In the previous class she learned how to find longest increasing sequence. She was given some interesting problems to solve but did nothing. So teacher gives her a task to solve now.

The problem is quite easy and straightforward. She is given an array $A$ with $n$ elements. She has to find how many continuous strictly increasing sequences with prime length in array $A$.

One more thing you should know about this lazy girl that she is so friendly and has a lot of friends. Nitu’s friends often complete her homework. Now she needs a friend to solve the task given by her teacher. Will you be a friend of Nitu?

Input

First line of input contains the number of test cases $T$ ($0 < T \le 10$). Next $T$ lines describe the case.

First line of each case contains an integer $n$ ($n \le 100000$), denoting the array size. Next line contains $n$ integers, denoting the elements of the array $A$ ($1 \le A[i] \le 1000000$).

Output

For each test case, output a single line that contains “Case X: Y” without any quote where $X$ denotes the number of test case and $Y$ denotes the answer of the problem.

Sample

Input	Output
2 4 1 2 3 4 3 10 11 21	Case 1: 5 Case 2: 3
In the second example the increasing sequences are: 10 (length with 1) 11 (length with 1) 21 (length with 1) 10 11 (length with 2), continuous strictly increasing sequence with prime length 10 11 21 (length with 3), continuous strictly increasing sequence with prime length 11 21 (length with 2), continuous strictly increasing sequence with prime length

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.