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 starts with an integer T (≤ 100), denoting the number of test cases.

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


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



Case 1: 1 2

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

hide comments
sherlock11: 2018-06-24 21:36:03

don't think it as hard problem..............setter is looking for O(1) solution........

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

First in Java. :)

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