Kevin喜欢一
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

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

氧气少年有一个文本输入框,最初文本输入框里只有一个字符 `\tt 1'。

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

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

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

输入描述:

第一行包含一个整数 T(1\leq T \leq 2\cdot 10^5),表示测试用例的组数。

对于每组测试用例:

仅输入一行,包含一个整数 n(1\leq n\leq 10^9)

输出描述:

对于每组测试用例:

仅输出一行,包含一个整数,表示答案。
示例1

输入

复制
2
1
2

输出

复制
0
1