Problem D. НОД и XOR
Input file name: gcd-xor.in
Output file name: gcd-xor.out
Time limit: 3 s
Memory limit: 256 MB

Для заданного числа N посчитайте количество пар целых чисел A и B, для которых

1 ≤ A ≤ B ≤ N
и
НОД{ A, B } = A ⊕ B,
где НОД{ A, B } — наибольший общий делитель чисел A и B, A ⊕ B — значение побитового исключающего «или» (или, что то же самое, результат поразрядного сложения по модулю два).

Input

Вход содержит T независимых тестов. В первой строке записано целое число T (1 ≤ T ≤ 1000). В каждой из последующих T строк записано целое число N (1 ≤ N ≤ 30 000 000).

Output

Выведите T строк, в каждой строке выведите номер теста и ответ. Придерживайтесь формата вывода, который указан в примере.

Example

gcd-xor.in gcd-xor.out
2
7
10000000
Case 1: 4
Case 2: 17440305