Antecedentes

Para celebrar el décimo aniversario de THUPC, el pequeño T y el pequeño S están preparando una gran celebración. El primer paso es determinar el recinto principal. Eligieron una habitación como sede y la decoraron con papel tapiz de bosque, muñecos de ajo gigantes y adornos de pared de "doble felicidad" (este año también es el 55.º aniversario de la Universidad de Tsinghua, en base 22) y decoraciones de plumas para que luzca ordenada. Sin embargo, el diligente pequeño T encontró un problema: el número de habitación colgado frente al recinto principal no parece lo suficientemente ordenado. El pequeño S sugirió tímidamente que se puede convertir el número a otra base para que se vea ordenado. En el proceso, descubrieron que existen muchas más formas de convertir la base para lograr este efecto. Por lo tanto, el pequeño T y el pequeño S decidieron convertir este interesante proceso de diseño del número de habitación en un desafío de entrada para la celebración, para que los asistentes lo resuelvan.

Descripción

El número de habitación del recinto principal determinado por el pequeño T y el pequeño S es $n$ en base decimal. El pequeño T define una representación "ordenada" de un número de habitación de la siguiente manera: para enteros positivos $b, p \ge 2$, si la representación en base $b$ del número de habitación $n$ consiste exactamente en varios segmentos de longitud $p$ formados por los mismos dígitos, entonces se considera que $(b, p)$ es una representación ordenada.

Formalmente, sea la representación en base $b$ de $n$ igual a $d_{k-1}d_{k-2} \dots d_1d_0$. Si existe un entero positivo $c$ tal que el número total de dígitos $k = cp$, y para todo $0 \le i < c$ se cumple que $d_{ip} = d_{ip+1} = \dots = d_{(i+1)p-1}$, entonces $(b, p)$ es una representación ordenada.

Por ejemplo, si el número de habitación es 2233 o 3355, entonces $(10, 2)$ es una representación ordenada; si el número de habitación es 1111, entonces $(10, 2)$ y $(10, 4)$ son dos representaciones ordenadas distintas; si el número de habitación es 6737151 (que en hexadecimal es 66CCFF), entonces $(16, 2)$ es una representación ordenada.

Para ganar la entrada al evento, debes responder a la pregunta del pequeño T y el pequeño S: ¿Cuántas representaciones ordenadas existen en total para el número de habitación del recinto principal?

Entrada

Cada caso de prueba contiene múltiples conjuntos de datos. La primera línea contiene un entero positivo $T$ ($1 \le T \le 10^3$), que representa el número de casos de prueba. Para cada conjunto de datos:

• La primera línea contiene un entero positivo $n$ ($1 \le n \le 10^{12}$), que representa el número de habitación del recinto principal.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $10^{12}$.

Salida

Para cada conjunto de datos, imprime una línea con un entero no negativo que represente la respuesta.

Ejemplos

Entrada 1

10
1
2
115
1111
2233
3355
191970
6737151
102934760424
618111100000

Salida 1

0
0
2
4
5
5
24
9
17
144

Nota

Para el tercer conjunto de datos, $115 = (55)_{22} = (11)_{114}$, por lo tanto, todas las representaciones ordenadas son $(22, 2)$ y $(114, 2)$.

Para el cuarto conjunto de datos, todas las representaciones ordenadas son $(10, 2), (10, 4), (100, 2), (1110, 2)$.