C. The Tale of the Magical Lantern Grid
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the heart of Agrabah, as the holy month of Ramadan began, the city came alive with the scent of spices, the sound of prayers, and the warmth of community. To celebrate this sacred time, the wise and beloved Sultan decided to create a grand display of lanterns symbolizing unity and harmony.

The Sultan commissioned an $$$n \times n$$$ mystical grid, where each lantern at position $$$(i, j)$$$ carried a special meaning. He explained to his trusted advisor, Aladdin, that the brightness of each lantern depended on the mathematical relationship between its row $$$i$$$ and column $$$j$$$.

The Rule of the Lanterns

  • If $$$i$$$ and $$$j$$$ are coprime (i.e., their greatest common divisor is $$$1$$$), the lantern shines brightly with a value of $$$i \times j$$$, symbolizing purity and harmony.
  • If $$$i$$$ and $$$j$$$ are not coprime, the lantern remains dark with a value of $$$0$$$, representing the absence of unity.

Example: $$$n=3$$$

Aladdin, eager to assist, was given the task of calculating the total brightness of all the lanterns in the grid. The Sultan believed that this total brightness would reflect the collective spirit of Agrabah during Ramadan.

To ensure the result remains manageable, the total brightness should be computed modulo $$$10^9 + 7$$$.

Can you help Aladdin solve this challenge and determine the total brightness of the magical lantern grid?

Input

The first line contains the number of test cases t ($$$1\le t \le 10^5$$$). Each test case consists of a single integer $$$n$$$ ($$$1\le n \le 10^5$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2.10^5$$$

Output

For each test case, print the total brightness of the magical lantern grid.

Example
Input
2
1
3
Output
1
23