B. Digital Products
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Define $$$d(x)$$$ as the product of digits of $$$x$$$. For example, $$$d(5442) = 5 \cdot 4 \cdot 4 \cdot 2 = 160$$$.

For a given integer $$$n$$$, define the set $$$D = \{ d(x) | 1 \le x \le n \}$$$. Find $$$|D|$$$.

In other words, find the number of different products of digits for all integers between $$$1$$$ and $$$n$$$.

Input

The first line contains one integer $$$t$$$ ($$$1\le t \le 1\;000$$$) — the number of test cases.

Each test case consists of one line containing the integer $$$n$$$ ($$$1 \le n \le 10^{18}$$$).

Output

For each test case, print the answer on a separate line.

Example
Input
6
1
5
10
20
100
1000
Output
1
5
10
10
37
101