时间限制：1s

空间限制：256MB

Description

大宇对减法和取模很感兴趣，因此他研究了两种操作。

具体来说，你可以进行 \(t\) 次询问，每次给出 \(n\) ，有如下两个操作可供选择：

1. ​ 选择一个整数 \(x\) ，满足 \(x>0\) ，将 \(n\) 变成 \(n−x\) ，即 \(n\gets n-x\) 。
   
2. ​ 选择一个整数 \(x\) ，满足 \(x>1\) ，将 \(n\) 变成 \(n\bmod x\) ，即 \(n\gets n\bmod x\) 。
   

定义一次操作的代价为选择的 \(x\) 的大小，大宇想知道使 \(n\) 变为 \(0\) 的最小操作代价。

Input Format

第一行输入一个数 \(t\) ，表示询问次数。
之后 \(t\) 行每行一个数 \(n\) ，表示每次需要变为 \(0\) 的数。

Output Format

一共 \(t\) 行，每行一个数表示最小操作代价。

Data Range

\(1\leq t\leq 10^5,\ 0\leq n\leq 10^{18}\) 。

Input Example #1：

1
3

Output Example #1：

3

Note

对于样例数据，使用一次操作 \(2\) ，选择 \(x=3\) 即可，最小代价为 \(3\) 。