Nitu the Laziest Girl

Rajib_119 Replay of Comilla Univers...
Limits 3s, 512 MB

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 AA with nn elements. She has to find how many continuous strictly increasing sequences with prime length in array AA.

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 TT (0<T100 < T \le 10). Next TT lines describe the case.

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

Output

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

Sample

InputOutput
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.

Submit

Login to submit.

Statistics

86% Solution Ratio
emrul_muEarliest, Dec '17
MR.Jukerburg11Fastest, 0.0s
shourov.sustLightest, 655 kB
ovis96Shortest, 882B
Toph uses cookies. By continuing you agree to our Cookie Policy.