You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

正整数 $n$ 的“成本”定义为将数字 $n$ 除以其各位数字之和的结果。

例如，数字 $104$ 的成本为 $\frac{104}{1 + 0 + 4} = 20.8$，而数字 $111$ 的成本为 $\frac{111}{1 + 1 + 1} = 37$。

给定一个正整数 $n$，它不包含前导零。你可以从数字 $n$ 中删除任意数量的数字（包括不删除任何数字），使得剩余的数字至少包含一位且严格大于零。剩下的数字不能重新排列。因此，最终可能得到一个包含前导零的数字。

例如，给定数字 $103554$。如果你决定删除数字 $1$、$4$ 和一个数字 $5$，最终得到数字 $035$，其成本为 $\frac{035}{0 + 3 + 5} = 4.375$。

你需要找出从数字中删除最少的数字，使得它的成本变成最小可能的值。

输入

第一行包含一个整数 $t$ ($1 \leq t \leq 1000$) —— 测试用例的数量。

每个测试用例的唯一一行包含一个正整数 $n$ ($1 \leq n < 10^{100}$)，该数字不包含前导零。

输出

对于每个测试用例，在新的一行输出一个整数 —— 需要从数字中删除的最少数字个数，以使其成本变为最小值。

4
666
13700
102030
7

2
4
3
0