Co-Prime Enemy Pair

Two integers A and B are known as co-prime or relatively prime if their greatest common divisor GCD (A, B) is equal to 1.

Now, if two integers A and B are co-prime and both of them have a single prime factor then they are known as Co-prime enemy pair. Definition of Co-prime enemy pair is, if two numbers are co-prime and individually in their prime factor have only one prime. As for example: 8, 9, 16 can be a part of co-prime enemy pairs as all of them have a single prime factor but 12, 20, 100 cannot be a part of co-prime enemy pairs as they have multiple prime factors.

Your task is to determine the total number of different co-prime enemy pairs within the range from 1 to N where N is a 32-bit integer.

Input

Input starts with an integer T (1 ≤ T ≤ 20) which represents number of test cases. Next, there are T lines where each line has a number N and 1 ≤ N ≤ 106.

Output

At first print test case number just like sample output “Case X: ”, X is the test case number. Then print the result.

Sample

Input	Output
2 1 4	Case 1: 0 Case 2: 2

Clarification for Case 2:

2, 3 and 4 – all the numbers have a single prime factor (for 2 and 4: the prime factor is 2 and for 3: the prime factor is 3). Next, we need to find out the total number of pairs we can make out of 2, 3 and 4 where the GCD of the pair is equal to 1. We can find two pairs of such type: (2, 3) and (3, 4). Therefore, the result is 2. Please remember that the pair (2, 3) and (3, 2) has no difference.