Nitu the Laziest Girl

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?


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


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.


1 2 3 4
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.