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.

Example

Input:
1
2
Output:
Case 1: 1 2

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