Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

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 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 (<= 10). Next T lines describe the case.

First line of each case contains an integer n (<= 100000), denoting the array size. Next line contains n integers, denoting the elements of the array. (1 <= A[i] <= 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.

Samples

InputOutput
2
4
1 2 3 4
3
10 11 21
Case 1: 5
Case 2: 3

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

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

Author
Discussion
Submit

Login to submit