13:I[87,["736","static/chunks/89fc4f0e-9e200ae6a0166583.js","401","static/chunks/363642f4-32903b9154b7835a.js","153","static/chunks/153-58eddeb032cc4608.js","131","static/chunks/131-05ce00cfd760e12b.js","87","static/chunks/87-b76b60eef573119a.js","286","static/chunks/app/problem/%5Bid%5D/page-45cf3875257fc32e.js"],"Header"] 14:I[1742,["736","static/chunks/89fc4f0e-9e200ae6a0166583.js","401","static/chunks/363642f4-32903b9154b7835a.js","153","static/chunks/153-58eddeb032cc4608.js","131","static/chunks/131-05ce00cfd760e12b.js","87","static/chunks/87-b76b60eef573119a.js","286","static/chunks/app/problem/%5Bid%5D/page-45cf3875257fc32e.js"],"ProblemView"] 15:T6a1,

Let's define $$$F(x)$$$ as the sum of the digits of $$$x$$$. An integer $$$x$$$ is considered beautiful if $$$F(F(x)) = F(x)$$$.

You are given an integer $$$x$$$. In one move, you can choose any digit in the number and replace it with another. The resulting number cannot have leading zeros.

Your task is to calculate the minimum number of moves (possibly zero) required to make the given number beautiful.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The only line of each test case contains a single integer $$$x$$$ ($$$1 \le x \le 10^{18}$$$).

Output

For each test case, print a single integer — the minimum number of moves (possibly zero) required to make the given number beautiful.

Note

In the first example, the given num

Beautiful Numbers

Examples