Background

From the finals of the 2026 Tsinghua University Student Programming Contest and Intercollegiate Invitational (THUPC2026).

Resources such as editorials can be found at https://github.com/dapingguo8/THUPC2026-final.

To celebrate the 10th anniversary of THUPC, Little T and Little S are preparing a grand 10th anniversary celebration.

The first step is to decide the main venue. They picked a room as the main venue and decorated it neatly with forest wallpaper, a huge garlic doll with no friends, a double "Xi" wall hanging (this year also happens to be Tsinghua's $(55)_{22}$-th anniversary celebration), and feather ornaments. However, the hardworking Little T noticed a thorny problem—the room number on the doorplate in front of the main venue did not look neat enough. Little S timidly suggested that they could make the room number look neat by converting it to another base. During their attempts, they found that there was more than one base conversion scheme that could make the room number neat. So Little T and Little S decided to turn this interesting room-number design process into the entry challenge for the celebration, and let all participants solve it.

Problem Description

The main venue room number chosen by Little T and Little S is $n$ in decimal. Little T gives the following definition of a neat representation of the room number: for integers $b, p \ge 2$, if the base-$b$ representation of $n$ is formed by concatenating several blocks of length $p$, where each block consists of the same digit, then $(b, p)$ is considered a neat representation.

Formally, let the base-$b$ representation of $n$ be $\overline{d_{k - 1} d_{k - 2} \dots d_1 d_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$ (whose hexadecimal representation is $\mathrm{66CCFF}$), then $(16, 2)$ is a neat representation.

To successfully win an entry ticket, you need to answer Little T and Little S's question: how many neat representations does the room number have in total?

Input Format

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

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

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

Output Format

For each test case, output one line with a non-negative integer, denoting the answer.

10
1
2
115
1111
2233
3355
191970
6737151
102934760424
618111100000

0
0
2
4
5
5
24
9
17
144

Hint

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

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

Translated by ChatGPT 5