一个数 $N$ 的阶乘，记作 $N!$，是所有介于 $1$ 到 $N$ 之间（包含 $1$ 和 $N$）的整数的乘积。例如，$5! = 120$。

每一个大于 $1$ 的整数都可以写成一个或多个质数的乘积，其中一些质数可能会重复。例如，$120 = 2 \times 2 \times 2 \times 3 \times 5$。

在本题中，我们关注一个数阶乘的质因数分解。你需要确定其质因数的总数以及不同质因数的个数。对于上述例子，$120$ 有 $5$ 个质因数（$2, 2, 2, 3, 5$）和 $3$ 个不同的质因数（$2, 3, 5$）。

输入格式

输入的第一行包含测试用例的数量 $C$ ($1 \leq C \leq 50$)。每个测试用例由一行组成，包含一个整数 $N$ ($2 \leq N \leq 100\,000$)。

输出格式

对于每个测试用例，输出一行 D T，其中 $D$ 是 $N!$ 的不同质因数的个数，$T$ 是 $N!$ 的质因数总数。

样例

样例输入 1

2
5
6

样例输出 1

3 5
3 7