题目描述

给定一个正整数 $n$，你需要在不超过 $n$ 的正整数中，选择一个正整数使其包含的质因数数量最大。

注意，在计算范围内某个数 $x$ 的质因数个数时，存在以下两种方式：

1. 允许重复：计算 $x$ 的所有质因数的个数时，每个质因数按其指数累加。

   例如 $x = 12 = 2^2 \times 3$，则质因数个数为 $2 + 1 = 3$。

2. 不允许重复：只计算 $x$ 的不同质因数的个数。

   例如 $x = 12$，质因数有 $2$ 和 $3$，个数为 $2$。

青藤不关心你选择了哪个数，你只需要对每个给定的 $n$，分别输出在这两种情况下的最大质因数数量。

注意 : 两种情况选择的 $x$ 可以不同。

输入格式

每个测试文件包含多组测试数据。

第一行输入一个整数 $t$（$1 \le t \le 10^5$），表示测试数据的组数。

接下来 $t$ 行，每行一个整数 $n$（$1 \le n \le 10^{15}$）。

输出格式

对于每组测试数据，输出一行两个整数，用空格隔开：

第一个整数表示 允许重复 时的最大质因数个数，第二个整数表示 不允许重复 时的最大质因数个数。

2
1
12

0 0
3 2

样例解释

• 对于 $n = 1$，显然不存在解，两个答案均为 $0$。
• 对于 $n = 12$，对于允许重复时可以选择 $12$，答案为 $3$，不允许重复时可以选择 $6$，答案为 $2$。