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\)