A. Locked Calculator
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

一个计算器上有 $$$0,1,2,3,4,5,6,7,8,9,+,-,\times,\div,=$$$ 这十五个按键。

现在所有的按键都被锁上了，给你一个非负整数 $$$n$$$ ，请问最少需要激活几个按键才能够打出这个数？

被激活的按键可以使用任意次。

Input

输入第一行包含一个整数 $$$T$$$ $$$(1\le{T}\le{10^3})$$$ ，代表测试组数。

随后 $$$T$$$ 行，每行包含一个非负整数 $$$n$$$ $$$(0\le{n}\le{10^{9}})$$$ 。

Output

输出 $$$T$$$ 行，代表第 $$$i$$$ 个测试点最少需要的按键数。

Example
Input
3
0
123
1296
Output
1
3
3
Note

对于 $$$0$$$ ，可以直接使用按键 $$$0$$$ 打出。

对于 $$$123$$$ ，可以直接使用按键 $$$1,2,3$$$ 打出。

对于 $$$1296$$$ ，可以使用按键 $$$6$$$ 和按键 $$$\times$$$ 打出 $$$6\times{6}\times 6\times 6$$$ ，再使用按键 $$$=$$$ 得到 $$$1296$$$ 。