题目描述

氧气少年 最近喜欢上了一。

氧气少年 有一个文本输入框，最初文本输入框里只有一个字符 1。

氧气少年 每次可以进行下面的操作：

• 选中文本输入框中的部分或全部字符，将选中的字符复制到剪贴板，然后立即将复制的内容粘贴到文本输入框末尾。

现在 氧气少年 想让文本输入框中恰好有 $n$ 个 1，请求出他需要做的最少的操作次数。

输入格式

第一行包含一个整数 $T(1≤T≤2*10^5)$，表示测试用例的组数。

对于每组测试用例：仅输入一行，包含一个整数 $n(1≤n≤10^9)$。

输出格式

对于每组测试用例：仅输出一行，包含一个整数，表示答案。

2
1
2

0
1