3056: Big Boss

Many years later, $Rainbow Island$ is in the mercy of big boss $qiami$. Big boss $qiami$ is fond of number $9$ because each side of the magic cube is made up of $9$ small pieces and he changes the face value of circulating currency to $9^{0}, 9^{1}, 9^{2}, 9^{3}, 9^{4}$ $Yuan$.

One day programmer $Uucloud$ went to a shop to buy Cat food worth $n$ $Yuan$. The shopkeeper $NoMoreWords$ and $Uucloud$ are good friends so he will give $Uucloud$ his change. $Uucloud$ wants to know how many bills do they need in their trade at least.

For example, if $Uucloud$ wants to buy cat food of $8$ $Yuan$, he will pay a $9$ Yuan bill and $NoMoreWords$ will give $Uucloud$ $1$ $Yuan$ bill as change. Two paper money are used in this trade. \\

The first line contains an integer number $T$, the number of test cases.

Next $T$ lines contains a number $n(1 \leq n \leq 10^{9} )$。

For each test case print the number of bills they need at least.

2
14
18

6
2