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.