Given a positive integer, N. 

Euler phi function denoted by \(\phi(n)\) counts the number of positive integers up to n that are co-prime to n.
Let us have a function F as:
\(F(x) = \sum_{i=1}^{x}\sum_{j=1}^{i}\phi(i) \times \phi(j)\)

Task
Your task is to calculate the value of F(N). Since the value can be large output it modulo \(10^9 + 7\).

Example

Assumptions

• N = 4

Approach

• \(F(4)\) = ( \(\phi(1).\phi(1)\) + \(\phi(2).\phi(1)\) + \(\phi(2).\phi(2)\) + \(\phi(3).\phi(1)\) + \(\phi(3).\phi(2)\) + \(\phi(3).\phi(3)\)  + \(\phi(4).\phi(1)\) + \(\phi(4).\phi(2)\) + \(\phi(4).\phi(3)\) + \(\phi(4).\phi(4)\) ) % ( \(10^9 + 7\) ).
• \(F(4)\)  = 23.

Function description

Complete the solve function provided in the editor. This function takes the following single parameter and returns the value of the function F:

• N: Represents the value of a number.
   

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

• The first line contains a single integer T, which denotes the number of test cases. T also specifies the number of times you have to run the solve function on a different set of inputs.
• For each test case:
  • First line contains a single integer denoting the value of N.

Output format

For each test case, print in a new line, a single integer denoting the value of F(N) mod  \(10^9 + 7\).
 

Constraints

\(1 \le T\le10^2\)
\(1 \le N \le 10^5\)
 

Code snippets (also called starter code/boilerplate code) 

This question has code snippets for C, CPP, Java, and Python.