View Russian Translation

For two integers a and b, integer d is their common divisors if and only if d divides both a and b. For example, 9 is a common divisor of $18$ and $27$, while 6 is not.

Among all common divisors of two integers a, b there always exists the largest one. Such a divisor is call the greatest common divisor, often denoted as $gcd(a, b)$, and it is one of the most fundamental concepts in number theory.

This problem focuses on $gcd$ function.

For a given integer Q the task is to answer Q queries, each one defined by a single integer n:

1. $superpowers(n) := \sum\limits_{i=1}^n n^i \cdot gcd(i, n)$
2. $superexps(n) := \sum\limits_{i=1}^n 2^{n + i} \cdot gcd(i, n)$
3. $superphis(n) := \sum\limits_{i=1}^n \varphi(n^i) \cdot gcd(i, n)$

where $\varphi(m)$ is called Euler’s totient function and it counts the positive integers $j \leq m$, for which $gcd(m, j) = 1$. For example, $\varphi(4) = 2$, because there are two integers not greater than 4, for which their greatest common divisor with 4 is 1, these numbers are 1 and 3.

Since all the above values can be very large, the goal is to compute their values modulo $10^9+7$.

Input format:

In the first line there is a single integer Q denoting the number of queries. In each of the following Q lines there are two integers t and n, where t is either $1, 2$ or 3 and denotes the type of the query, and n denotes the parameter of the query.

Output format:

Output exactly Q lines. In the $i^{th}$ of them output the answer to the $i^{th}$ query computed modulo $10^9+7$.

Constraints:

$1 \leq Q \leq 10^5$
$1 \leq N \leq 10^5$