4-2 大宇的数字零

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制: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\) 。

2023暑假集训7月8日训练题

未参加
状态
已结束
规则
ACM/ICPC
题目
6
开始于
2023-07-08 09:00
结束于
2023-07-08 11:00
持续时间
2.0 小时
主持人
参赛人数
22