Problem Description

每一个正整数都可以表示成m = An-1(n-1)! + An-2(n-2)! + An-3(n-3)! + ... + A1, (0<=Ai<=i, j =1, 2, ..., n-1)的形式. 但是对于一个给定的正整数, ACboy的老师要他找出最小的min(An-1 + An-2 + .. + A1)满足m = An-1(n-1)! + An-2(n-2)! + An-3(n-3)! + ... + A1.
你能帮帮他吗?

Input

输入首先给出一个N, 代表有N个测试实例。
接下来的N行, 每行包括一个正整数M (1 <= M < 2^32).

Output

对于每个测试实例输出min(An-1 + An-2 + .. + A1).

3
2
3
100

1
2
6

Hint

对于2, 可以写成3 = 1*2!, 所以答案为1.
对于3, 可以写成3 = 1*2! + 1*1!, 所以答案为2.
对于100, 可以写成100 = 4*4! + 2*2!, 所以答案为6.

Author

8600