OVGDEL - Good Elements

no tags 

You are given a sequence consisting of integers a1, a2, a3, …, an. Any element ai is called good if there exists another element aj in the sequence (i≠j) such that aj is a non-negative power of ai. In other words ai is called good if there exists an element aj where i≠j and aj=aik for some k>=0.

For example, consider the following sequence: [2, 4, 4, 6, 3, 8]. This sequence contains 3 good elements. The 1st, 2nd and 3rd elements are good.

1st element “2” is good because there exists “4” and “8” in the different positions of the sequence which are non negative power of “2” (22=4, 23=8). 2nd element “4” is good because there exists another “4” in a different position of the sequence which is a non-negative power of “4” (41=4). Same applies for the 3rd element.


Given the sequence, now you have to find out total number of good elements in the sequence.

Input

The first line contains an integer t denoting the number of test cases.

For every test case the first line contains the integer n the length of the given sequence. The second line contains the sequence of integers a[1], a[2], a[3], …, a[n].

Constraints

1<=t<=10

1<=n<=104

1<=ai<=106

Output

For each test case print the case number followed by the result in a single line according to the following format "Case X: R" (without quotes), where X denotes the case number and R denotes the result. See the sample for further clarification.

Example

Input:

3

6

2 4 4 6 3 8

2

1 2

2

10 100

Output:

Case 1: 3

Case 2: 1

Case 3: 1


[ This Problem Orginally Contributed by Hafiz Al Masud Ovi ]


Added by:Avik Sarkar
Date:2018-07-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own