You are given an integer \(N\) and there is a function \(F(N)=\sum_{i=1}^{N} GCD(X,i)\). Here, GCD denotes the greatest common divisor. You are required to select an integer value \(X\) that is greater than or equal to 1.

Your task is to determine the following:

The maximum possible value of \(F(N)\) that you can get
The minimum \(X\) for which maximum value will be achieved

Input format

The first line contains an integer \(T\) denoting the number of test cases.
Next \(T\) lines contain a single integer \(N\).

Output format

Print \(T\) lines. For each test case:

Print a single line containing two integers, the maximum value of \(F(N)\) and the minimum value of \(X\) for which \(F(N)\) is maximized.

Constraints

\(1 \leq T \leq 40\)

\(1 \leq N \leq 40\)