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 ≤ 10⁶).

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

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