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$