Description

Alice 准备抢走 Bob 的私房钱。为了增加趣味性，他们决定玩一个游戏：

游戏开始时，Bob 拿出 枚硬币给 Alice。此时 Alice 手中有 1 枚硬币，Bob 手中有 $n$ 枚硬币。

接下来，Alice 可以重复进行以下操作，直到拿走 Bob 手中的全部硬币：

假设当前 Alice 手中有 $A$ 枚硬币，Bob 手中有 $B$ 枚硬币。每次转移 Alice 选择一个正整数 $k$，满足 $k=\gcd(A, B)^{1}$，并将 $k$ 枚硬币从 Bob 手中转移到自己手中。

请问 Alice 最少需要进行多少次操作，才能拿走 Bob 手中的全部硬币？

*$^1$$\gcd(A,B)$ 表示 $A$ 与 $B$ 的最大公约数。

Format

Input

本题包含多个测试数据，第一行包含一个整数 $T$ 满足$1\leq T\leq 3\times 10^3$，表示测试数据组数。

接下来 $t$ 行每行包含一个整数 $n$ 满足 $1\leq n \leq 1\times 10^9$，表示 Bob 手中硬币的数量。

Output

输出共 $T$ 行，每行输出一个整数，表示对应测试数据的最少操作次数。

Samples

3
5
18
9

3
18
5

Note

在第三组测试用例中，$A=1,B=9$ 时，其转移过程为 $(1,9)\to (2,8)\to (4,6)\to (6,4)\to (8,2)\to (10,0)$ 一共 $5$ 次操作。