Cannot parse: (0 , import_utils.normalizeSubtasks) is not a function or its return value is not iterable

Background

数学，嗯，还是挺美的。

Description

有一个大于 1 的正整数 n ，需要将之质因子分解，并按质因子从小到大的格式输出，例如该整数为 24，则输出 24=2^3*3^1 。并在下一行输出该整数的因子个数。

多组测试

Format

Input

第一行一个整数 t ，表示有 t 组测试

每组输入有一行一个整数 n

Output

输出共 t 组，每组输出有两行，第一行按格式输出质因子分解式，第二行一个整数表示该整数因子的个数。

Samples

3
2
16
24

2=2^1
2
16=2^4
5
24=2^3*3^1
8

Limitation

t ≤ 500

2 ≤ n ≤ 5000000