G. Less is More
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a number $$$n$$$. Consider all pairs of natural numbers $$$a$$$ and $$$b$$$.

Your task is to find out how many distinct values of number $$$m$$$ satisfy the following equation:

$$$$$$ \forall (a, b) \in \mathbb{N}, (a+b)^n \equiv a^n + b^n \pmod m$$$$$$

Input

The first line contains a single integer number $$$(1 \le T \le 3 \times 10^5)$$$, the number of test cases.

Each test case contains a single integer $$$(2 \le n \le 10^6)$$$.

Output

You should print a single integer number (the distinct possible values of $$$m$$$ mod $$$1000000007$$$) for each testcase.

Example
Input
2
3
4
Output
4
2