Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Divisor Difference

Limits: 1s, 512 MB

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 i.e (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 denoting the number of testcase. Next T lines contain one integer N which is described above.

1<=T<=20

2<=N<=10^9

Output

Print case no and X-Y separating by a single space. For more clearification see sample testcase.

Samples

InputOutput
3
2
4
6
Case #1: 1
Case #2: 0
Case #3: 1

Problem Setter: Md. Masud Mazumder

Discussion