1005. GCD

题目描述

小 H 和小 M 玩游戏。

在游戏开始，小 H 会有一个整数 $x$，小 M 每次操作会找到两个正整数 $a, b$（满足 $a\times b = x$ 且 $\max\{a, b\} > 1$），之后再把 $a, b$ 的 gcd 还给小 H。

小 M 笨笨的，她想知道这个游戏最多会进行几轮

输入格式

第一行输入一个整数 $T（T\le 200）$ 表示数据组数。

接下来 $T$ 行，每行一个整数 $x（1\le x \le 10^{18}）$，表示最开始小 $H$ 手里的整数

输出格式

$T$ 行，每行一个整数，表示这组数据对应的答案。

样例输入

3
4
5
9

样例输出

2
1
2

来源：2026杭电多校-测试专用（四川大学） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1231&pid=1005