THUPC 10周年を記念して、小Tと小Sは盛大な10周年記念式典を準備しています！

式典の最初の準備作業は、メイン会場を決定することです。彼らはある部屋をメイン会場として選び、森の壁紙、巨大なニンニクのぬいぐるみ、対の「囍」の壁掛け（今年はちょうど清華大学の55周年記念でもあります）、そして羽毛の飾りでそれをきれいに装飾しました。しかし、真面目な小Tは一つの厄介な問題に気づきました。メイン会場の前に掲げられた部屋番号が、どうも整っていないように見えるのです。小Sは控えめに、進数変換を行うことで部屋番号を整えられるのではないかと提案しました。試行錯誤する中で、彼らは部屋番号を整える効果を持つ進数変換の方法が一つではないことに気づきました。そこで、小Tと小Sはこの面白い部屋番号のデザイン過程を式典の入場チャレンジとし、参加する皆さんに解いてもらうことにしました。

小Tと小Sが決定したメイン会場の部屋番号は、10進数で $n$ です。小Tは「整った」部屋番号の表現方法について、次のように定義しました。正の整数 $b, p \ge 2$ に対して、部屋番号 $n$ の $b$ 進数表記が、長さ $p$ の同じ数字の列がいくつか連結されたものになっている場合、$(b, p)$ は一つの「整った」表現方法であるとみなします。

形式的に述べると、$n$ の $b$ 進数表記を $d_{k-1}d_{k-2} \dots d_1d_0$ としたとき、総桁数 $k = cp$ となる正の整数 $c$ が存在し、かつすべての $0 \le i < c$ に対して $d_{ip} = d_{ip+1} = \dots = d_{(i+1)p-1}$ が成り立つならば、$(b, p)$ は一つの「整った」表現方法です。

例えば、部屋番号が $2233$ や $3355$ の場合、$(10, 2)$ は一つの整った表現方法です。部屋番号が $1111$ の場合、$(10, 2)$ と $(10, 4)$ は二つの異なる整った表現方法です。部屋番号が $6737151$（16進数表記で $66CCFF$）の場合、$(16, 2)$ は一つの整った表現方法です。

入場チケットを勝ち取るために、小Tと小Sの問いに答えてください。メイン会場の部屋番号には、合計で何種類の整った表現方法が存在しますか？

各テストケースには複数のテストデータが含まれます。入力の最初の行には、データセットの数を示す正の整数 $T$ ($1 \le T \le 10^3$) が含まれます。各テストデータについて：

• 最初の行には、メイン会場の部屋番号を示す正の整数 $n$ ($1 \le n \le 10^{12}$) が含まれます。

すべてのテストデータにおける $n$ の総和は $10^{12}$ を超えないことが保証されています。

各テストデータについて、答えとなる非負整数を1行に出力してください。

入出力例

入力 1

10
1
2
115
1111
2233
3355
191970
6737151
102934760424
618111100000

出力 1

0
0
2
4
5
5
24
9
17
144

注記

3番目のテストデータについて、$115 = (55)_{22} = (11)_{114}$ であるため、すべての整った表現方法は $(22, 2), (114, 2)$ です。

4番目のテストデータについて、すべての整った表現方法は $(10, 2), (10, 4), (100, 2), (1110, 2)$ です。