互质集合

题目描述

$T$组询问，每次给一个数$n$，问$\{1, 2, \dots, n\}$中有多少个非空子集，满足这些数的最大公约数是$1$。输出答案对$10^9+7$取模的结果。

输入格式

第一行一个整数$T$。

接下来$T$行，每行一个整数$n$。

输出格式

一共$T$行，每行一个数，表示答案。

样例输入

3
10
1000
1000000

样例输出

983
912086516
822856275

数据范围

对于所有数据，保证$1\leq T\leq 1000, 1\leq n \leq 10^7$。