D. Pairwise Coprime Set
time limit per test
1 second
memory limit per test
256 megabytes
input
stdin
output
stdout

Two positive numbers are called coprime (or relatively prime) if their greatest common divisor is 1. A set of integers is said to be pairwise coprime if for every pair of different element (a, b), a and b are co-prime.

Given set S of N first positive integers, your task is to find the largest subset S' of S such that S' is pairwise coprime.

Input

The first line of input is the number T - the number of tests (T ≤ 1000). Then T tests follow. Each test will be printed in one line with the number N. (1 ≤ N ≤ 106)

Output

For each test, print Case#i: p where i is the 1-based index of the test and p is the size of the largest subset.

Examples
Input
1
5
Output
Case #1: 4
Note

{1, 2, 3, 5} and {1, 3, 4, 5} are the largest pairwise coprime subset.