题目描述

AtCoder 王国流通面额为

日元的纸币，每种纸币都有无限张。

Alice 要支付恰好 $N$ 日元。她可以先向店员交付总额不少于 $N$ 日元的纸币，店员再用上述纸币找零。

请最小化 Alice 交出的纸币张数与店员找回的纸币张数之和。

更形式化地，对于整数 $M\ge N$，设用上述纸币凑出 $M$ 日元所需的最少张数为 $f(M)$，则需要求

共有 $T$ 组测试数据，请分别求解。

限制条件

• $1\le T\le 10^4$
• $1\le N\le 10^{18}$
• 所有输入均为整数。

输入

T
N_1
N_2
...
N_T

输出

输出 $T$ 行，第 $i$ 行输出第 $i$ 组测试数据的答案。

样例输入 1

3
7
34
123456789123456789

样例输出 1

4
7
44

对于第一组测试数据，可以交出一张 $10$ 日元纸币，再收回三张 $1$ 日元纸币，共使用 $4$ 张纸币。