题目描述

根据唯一分解定理，每个大于 $1$ 的正整数都能唯一地写成若干个质数的乘积。例如 $360 = 2^3 \times 3^2 \times 5$。

现在给出 $q$ 个正整数，请你对每个数 $n$ 完成两件事：

1. 把 $n$ 分解质因数，按下面的格式输出：先写 n=，然后把各个质因子从小到大用 * 连接起来；如果某个质因子出现了不止一次，写成 质因子^指数 的形式，指数为 $1$ 时不写 ^1。整行不含空格。
2. 输出 $n$ 一共有多少个正约数（包括 $1$ 和 $n$ 本身）。

输入格式

第一行一个整数 $q$，表示询问的个数。

接下来 $q$ 行，每行一个整数 $n$。

输出格式

对每个询问输出两行：第一行是 $n$ 的质因数分解式，第二行是一个整数，表示 $n$ 的正约数个数。

样例 #1

样例输入 #1

4
360
97
1024
1001

样例输出 #1

360=2^3*3^2*5
24
97=97
2
1024=2^10
11
1001=7*11*13
8

样例解释

• $360 = 2^3 \times 3^2 \times 5$。它的每个约数都形如 $2^a \times 3^b \times 5^c$，其中 $a$ 有 $0 \sim 3$ 共 $4$ 种取法，$b$ 有 $3$ 种，$c$ 有 $2$ 种，所以约数个数是 $4 \times 3 \times 2 = 24$。
• $97$ 是质数，分解式就是它自己，约数只有 $1$ 和 $97$ 两个。
• $1024 = 2^{10}$，约数是 $2^0, 2^1, \dots, 2^{10}$ 共 $11$ 个。
• $1001 = 7 \times 11 \times 13$，约数个数是 $2 \times 2 \times 2 = 8$。

提示

数据范围

• 对于 $40\%$ 的数据：$n \le 10^6$；
• 对于 $70\%$ 的数据：$n \le 10^9$；
• 对于 $100\%$ 的数据：$1 \le q \le 10$，$2 \le n \le 10^{12}$。

提示

• 若 $n = p_1^{e_1} \times p_2^{e_2} \times \dots \times p_k^{e_k}$，则 $n$ 的正约数个数是 $(e_1 + 1) \times (e_2 + 1) \times \dots \times (e_k + 1)$。
• 试除时只需要试到 $\sqrt n$。想一想：试除结束后，如果剩下的数还大于 $1$，它是什么？