GGD - Mr Toothless and His GCD Operation

no tags 

 

You are given N. You have to find two numbers a and b such that GCD (a, b) is as maximum as possible where 1<=a<b<=N.

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case contains an integer N (2 ≤ N ≤ 106).

Output

For each case, print the case number and then print a and b. If there exists multiple solutions print the one where a+b is maximum.

Sample Input/Output

Sample Input

Sample Output

1

2

Case 1: 1 2

Problem Setter: Md Abdul Alim, Department of CSE, Bangladesh University of Business & Technology


hide comments
Bhumit: 2016-09-17 07:15:57

First in Java. :)


Added by:Md Abdul Alim
Date:2014-05-12
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:Own Problem