Coprime Subsets

Problem Description

There are $T$ queries. Each query gives a number $n$; count how many non-empty subsets of $\{1, 2, \dots, n\}$ have greatest common divisor equal to $1$. Output the answer modulo $10^9 + 7$.

Input Format

The first line contains one integer $T$.

Each of the next $T$ lines contains one integer $n$.

Output Format

Output $T$ lines, each containing one number: the answer.

Sample Input

3
10
1000
1000000

Sample Output

983
912086516
822856275

Constraints

For all test cases, $1 \le T \le 1000$ and $1 \le n \le 10^7$.