D. Modulo maths
time limit per test
0.25 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

Birute loves modular arithmetics, but hates long problem statements.

Given n, find f(n).

Input

The first line contains the number of test cases T (T ≤ 50). In the following T lines there are integer values of number n (1 ≤ n ≤ 10007).

Output

For each test case output one line containing “Case #tc: num”, where tc is the number of the test case (starting from 1) and num is the value of f(n).

Examples
Input
2
1
2
Output
Case #1: 1
Case #2: 0
Note

Fun fact: 1 is neither prime nor composite number.