K

Quad

John is learning number theory. His first lesson is about prime numbers. Like everyone, he loves prime numbers. Unlike everyone, he started trying to generalize the idea of prime numbers. He first tried to generalize the idea of prime numbers to a pair of number (a, b). To generalize he needed to define addition and multiplication. He defined addition and multiplication and a function abs() in following way,

            (a1, b1) + (a2, b2) = (a1+b1, a2+b2)

            (a1, b1) * (a2, b2) = (a1*a2 - b1*b2, a1*b2 + a2*b1)

            abs((a, b)) = sqrt(a2+b2)

He proved that if z1, z2 and z3 are pair of numbers then,

            z1*z2 = z2*z1

            z1*(z2+z3) = z1*z2 + z1*z3

            abs(z1*z2)=abs(z1)*abs(z2)

He says a pair of number to be prime if it cannot be written as a multiplication of two integer pair of numbers both having absolute value greater than 1. So (2, 1) is prime while (5, 5) = (2, 1) * (3,1) is not. Note that in this system prime factorization is not necessarily unique. As an example (5, 0) = (1, 2) * (1, 2) = (2, 1) * (2, -1). The absolute value of (3, 4) is abs((3,4)) = 5.

He wants to extend the idea further. He says a pair of pair or quad (p, q) where both p and q are pair of integer. Multiplication, addition and absolute value are defined as below.

            (p1, q1) + (p2, q2) = (p1+q1, p2+q2)

            (p1, q1) * (p2, q2) = (p1*p2 – q1*q2, p1*q2 + p2*q1)

            abs((p, q)) = sqrt( abs(p)2 + abs(q)2 )

For example,

( (1, 2) , (3, 4) ) + ( (5, 6) , (7, 8) ) = ( (6, 8) , (10, 12) )

( (1, 2) , (3, 4) ) * ( (5, 6) , (7, 8) )

= ( (1, 2) * (5, 6) - (3, 4) * (7, 8) , (1, 2) * (7, 8)  + (3, 4) * (5, 6) )

= ( (-7, 16) - (-11, 52) , (-9, 22) + (-9, 38) )

= ( (4, -36),(-18,60) )

He proved that if z1, z2 and z3 are quads then,

            z1*z2 = z2*z1

            z1*(z2+z3) = z1*z2 + z1*z3

            abs(z1*z2)=abs(z1)*abs(z2)

Again he will say a quad (p, q) to be integer if both p and q are integer pairs. A quad is said to be prime if it cannot be written as multiplication of two quads both having absolute value greater than 1. For example, ( (4, -36) , (18, 60) ) is not a prime while ( (5,2), (1,1) ) is.

John says a real number x to be cool if there is a quad z such that z is prime and abs(z)=x. So sqrt(31) is cool as abs(((5,2), (1,1))) = sqrt(31). John is wondering how many cool numbers are there which are not greater than a certain number.

Input

The first line of input will contain T (≤ 1000) denoting the number of cases.

Each case starts with a line containing an integer n (0 < n < 104).

Output

For each case, print the case number and the number of cool numbers not greater than n.

Sample Input

Output for Sample Input

 
2
2
4
 
Case 1: 2
Case 2: 6

Problem Setter: Tanaeem M Moosa, Special Thanks: Jane Alam Jan