Tło

Aby uczcić dziesiątą rocznicę THUPC, Mały T i Mały S przygotowują wielką uroczystość! Pierwszym zadaniem jest wyznaczenie głównej sali. Wybrali oni pomieszczenie i udekorowali je tapetami w las, ogromnymi pluszowymi czosnkami, ściennymi dekoracjami z podwójnym znakiem „szczęścia” (w tym roku przypada akurat 55. rocznica powstania uniwersytetu Tsinghua) oraz ozdobami z piór, aby wszystko wyglądało schludnie. Jednak pracowity Mały T zauważył problem: numer sali wiszący przed wejściem nie wygląda wystarczająco schludnie. Mały S nieśmiało zasugerował, że można zmienić system liczbowy, aby numer sali stał się schludny. Podczas prób odkryli, że istnieje wiele sposobów na osiągnięcie tego efektu poprzez zmianę podstawy systemu. W rezultacie Mały T i Mały S postanowili uczynić ten ciekawy proces projektowania numeru sali wyzwaniem dla uczestników uroczystości.

Numer sali głównej wyznaczony przez Małego T i Małego S w systemie dziesiętnym to $n$. Mały T definiuje „schludny” sposób zapisu numeru sali w następujący sposób: dla liczb całkowitych $b, p \ge 2$, jeśli zapis liczby $n$ w systemie o podstawie $b$ składa się dokładnie z kilku segmentów o długości $p$, z których każdy składa się z takich samych cyfr, to $(b, p)$ uznaje się za schludny sposób zapisu.

Formalnie, niech zapis liczby $n$ w systemie o podstawie $b$ będzie postaci $d_{k-1}d_{k-2} \dots d_1d_0$. Jeśli istnieje liczba całkowita $c$ taka, że całkowita liczba cyfr wynosi $k = cp$ oraz dla wszystkich $0 \le i < c$ zachodzi $d_{ip} = d_{ip+1} = \dots = d_{(i+1)p-1}$, to $(b, p)$ jest schludnym sposobem zapisu.

Na przykład, jeśli numer sali to 2233 lub 3355, to $(10, 2)$ jest schludnym sposobem zapisu; jeśli numer sali to 1111, to $(10, 2)$ oraz $(10, 4)$ są dwoma różnymi schludnymi sposobami zapisu; jeśli numer sali to 6737151 (zapis szesnastkowy to 66CCFF), to $(16, 2)$ jest schludnym sposobem zapisu.

Aby pomyślnie zdobyć bilet wstępu, musisz odpowiedzieć na pytanie Małego T i Małego S: ile łącznie istnieje schludnych sposobów zapisu numeru sali głównej?

Wejście

Każdy zestaw danych zawiera wiele przypadków testowych. Pierwsza linia wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 10^3$), oznaczającą liczbę przypadków testowych. Dla każdego przypadku testowego:

• Pierwsza linia zawiera liczbę całkowitą $n$ ($1 \le n \le 10^{12}$), oznaczającą numer sali głównej.

Gwarantuje się, że suma $n$ we wszystkich przypadkach testowych nie przekracza $10^{12}$.

Wyjście

Dla każdego przypadku testowego wypisz w jednej linii nieujemną liczbę całkowitą oznaczającą odpowiedź.

Przykład

Wejście 1

10
1
2
115
1111
2233
3355
191970
6737151
102934760424
618111100000

Wyjście 1

0
0
2
4
5
5
24
9
17
144

Uwagi

Dla trzeciego przypadku testowego $115 = (55)_{22} = (11)_{114}$, zatem wszystkie schludne sposoby zapisu to $(22, 2)$ oraz $(114, 2)$.

Dla czwartego przypadku testowego wszystkie schludne sposoby zapisu to $(10, 2), (10, 4), (100, 2), (1110, 2)$.