Divisor Difference

If you have solved the previous problem, the problem setter is congratulating you. Now focus on your next problem.

In this problem you will be given an integer $ N $ where $ N = XY $. Your task is to find the $ X - Y $ so that $ X - Y $ is minimized.

Input

First line of input contains an integer T (1 ≤ T ≤ 20) denoting the number of testcase.

The next T lines contain one integer N (2 ≤ N ≤ 109) which is described above.

Output

Print "Case #n: v" where n is the case number and v is $ X-Y $.

Sample

Input	Output
3 2 4 6	Case #1: 1 Case #2: 0 Case #3: 1

Problem Setter: Md. Masud Mazumder