Le numéro de la salle principale déterminé par Xiao T et Xiao S est $n$ en base dix. Xiao T définit une représentation « ordonnée » du numéro de salle comme suit : pour des entiers positifs $b, p \ge 2$, si la représentation en base $b$ du numéro de salle $n$ est composée exactement de plusieurs segments de longueur $p$ constitués de chiffres identiques, alors $(b, p)$ est considérée comme une représentation ordonnée.

Formellement, soit la représentation en base $b$ de $n$ égale à $d_{k-1}d_{k-2} \dots d_1d_0$. S'il existe un entier positif $c$ tel que le nombre total de chiffres $k = cp$, et que pour tout $0 \le i < c$, on ait $d_{ip} = d_{ip+1} = \dots = d_{(i+1)p-1}$, alors $(b, p)$ est une représentation ordonnée.

Par exemple, si le numéro de salle est 2233 ou 3355, alors $(10, 2)$ est une représentation ordonnée ; si le numéro de salle est 1111, alors $(10, 2)$ et $(10, 4)$ sont deux représentations ordonnées distinctes ; si le numéro de salle est 6737151 (représenté en hexadécimal par 66CCFF), alors $(16, 2)$ est une représentation ordonnée.

Afin de gagner votre billet d'entrée, vous devez répondre à la question de Xiao T et Xiao S : combien existe-t-il de représentations ordonnées au total pour le numéro de la salle principale ?

Entrée

Chaque cas de test contient plusieurs jeux de données. La première ligne de l'entrée contient un entier positif $T$ ($1 \le T \le 10^3$), représentant le nombre de jeux de données. Pour chaque jeu de données :

• La première ligne contient un entier positif $n$ ($1 \le n \le 10^{12}$), représentant le numéro de la salle principale.

Il est garanti que la somme de $n$ sur tous les jeux de données ne dépasse pas $10^{12}$.

Sortie

Pour chaque jeu de données, affichez sur une ligne un entier non négatif représentant la réponse.

Exemples

Entrée 1

10
1
2
115
1111
2233
3355
191970
6737151
102934760424
618111100000

Sortie 1

0
0
2
4
5
5
24
9
17
144

Remarque

Pour le troisième jeu de données, $115 = (55)_{22} = (11)_{114}$, donc toutes les représentations ordonnées sont $(22, 2)$ et $(114, 2)$.

Pour le quatrième jeu de données, toutes les représentations ordonnées sont $(10, 2), (10, 4), (100, 2), (1110, 2)$.