The main venue room number determined by Xiao T and Xiao S is $n$ in decimal. Xiao T gives the following definition for a "neat" representation of a room number: for positive integers $b, p \ge 2$, if the base-$b$ representation of the room number $n$ consists exactly of several segments of length $p$ with identical digits concatenated together, then $(b, p)$ is considered a neat representation.

Formally, let the base-$b$ representation of $n$ be $d_{k-1}d_{k-2} \dots d_1d_0$. If there exists a positive integer $c$ such that the total number of digits $k = cp$, and for all $0 \le i < c$, it holds that $d_{ip} = d_{ip+1} = \dots = d_{(i+1)p-1}$, then $(b, p)$ is a neat representation.

For example, if the room number is $2233$ or $3355$, then $(10, 2)$ is a neat representation; if the room number is $1111$, then $(10, 2)$ and $(10, 4)$ are two different neat representations; if the room number is $6737151$ (which is $66CCFF$ in hexadecimal), then $(16, 2)$ is a neat representation.

To successfully win an entrance ticket, you need to answer Xiao T and Xiao S's question: how many neat representations exist for the main venue's room number?

Input

Each test case contains multiple test data. The first line contains a positive integer $T$ ($1 \le T \le 10^3$), representing the number of test cases. For each test case:

• The first line contains a positive integer $n$ ($1 \le n \le 10^{12}$), representing the room number of the main venue.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^{12}$.

Output

For each test case, output a single non-negative integer on a line, representing the answer.

Examples

Input 1

10
1
2
115
1111
2233
3355
191970
6737151
102934760424
618111100000

Output 1

0
0
2
4
5
5
24
9
17
144

Note

For the third test case, $115 = (55)_{22} = (11)_{114}$, so all neat representations are $(22, 2)$ and $(114, 2)$.

For the fourth test case, all neat representations are $(10, 2), (10, 4), (100, 2), (1110, 2)$.