The factorial of a number $N$, written $N!$, is the product of all integers between $1$ and $N$, inclusively. For example, $5! = 120$.

Every integer greater than $1$ can be written as the product of $1$ or more prime numbers, some of which may repeat. For example, $120 = 2 \times 2 \times 2 \times 3 \times 5$.

For this problem, we are interested in the prime factorization of the factorial of a number. You will need to determine the number of total and distinct prime factors. For the example above, there are $5$ total prime factors ($2$, $2$, $2$, $3$, $5$) and $3$ distinct prime factors ($2$, $3$, $5$).

Input

The first line of input will contain the number of test cases, $C$ ($1 \leq C \leq 50$). Each test case will consist of a single line containing an integer $N$ ($2 \leq N \leq 100\,000$).

Output

Each test case will result in a single line of output D T where $D$ is the number of distinct prime factors of $N!$ and $T$ is the total number of prime factors of $N!$.

Sample Input

2
5
6

Sample Output

3 5
3 7