Make numbers

Limits: 2 sec., 512 MiB

This statement was translated automatically from Ukrainian.

Marichka has a favorite number \(n\), which has length \(len\) in decimal notation. Marichka loves to make all numbers from 1 to \(n\) using exactly \(len\) blocks. If the number that Marichka is currently making has fewer than \(len\) digits, she adds leading zeros.

Marichka asked Zenyk to make such blocks so that she could make any number from 1 to \(n\). Each of the blocks has 6 faces and Marichka can choose any subset of \(len\) blocks and arrange them in arbitrary order and orientation.

Zenyk is very lazy, so he wants to make as few blocks as possible. What is the minimum number of blocks needed to be able to make all the numbers?

Note that a block with the digit \(6\) can be turned upside down to get \(9\).

Input

The first line gives a single integer \(t\) — the number of test cases.

Each of the following \(t\) lines gives a single integer \(n\).

Output

In \(t\) lines, print the minimum number of blocks for the corresponding \(n\).

Constraints

\(1 \le t \le 10^4\),

\(1 \le n \le 10^{18}\).

Samples