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\)
N is 3 so F(3)=GCD(1,x)+GCD(2,x)+GCD(x,3)
If we choose x=6 we will get F(3)=GCD(1,6)+GCD(2,6)+GCD(3,6)=6.
There is no smaller value than X=6 for which F(3)=6. Also no other value of X we can get a greater value of F(3).
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor