You are given a sequence consisting of integers a₁, a₂, a₃, …, a_n. Any element a_i is called good if there exists another element a_j in the sequence (i≠j) such that a_j is a non-negative integral power of a_i. In other words a_i is called good if there exists an element a_j where i≠j and a_j=a_i^k for some integer 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” (2²=4, 2³=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” (4¹=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<=10⁴

1<=a_i<=10⁶

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 originally contributed by Hafiz Al Masud Ovi ]