一个计算器上有 0,1,2,3,4,5,6,7,8,9,+,−,×,÷,= 这十五个按键。

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

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

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

随后 T 行，每行包含一个非负整数 n (0≤n≤10^9) 。

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

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

对于 1296 ，可以使用按键 6 和按键 × 打出 6×6×6×6 ，再使用按键 = 得到 1296 。