題目背景

為了慶祝 THUPC 十週年，小 T 和小 S 正在籌備一場盛大的十週年慶典！

慶典的首要準備工作是確定主會場。他們選定了一個房間作為主會場，並用森林牆紙、碩大無朋的大蒜玩偶、雙「囍」壁掛（今年恰好也是清華 $(55)_{22}$ 週年校慶）和羽毛擺件把它裝飾得整整齊齊。然而，兢兢業業的小 T 發現了一個棘手的問題：赫然掛在主會場前的門牌上的房間號看起來不夠整齊。小 S 弱弱地提出，可以通過轉換進位的方式，讓房間號變得整齊。在嘗試的過程中，他們發現能讓房間號達到整齊效果的進位轉換方案遠不止一種。於是，小 T 和小 S 決定將這個有趣的房間號設計過程作為慶典的入場挑戰，交由前來參會的大家解答。

小 T 和小 S 確定的主會場房間號在十進位下為 $n$。小 T 對「整齊」的房間號表示方式給出了如下定義：對於正整數 $b, p \ge 2$，若房間號 $n$ 的 $b$ 進位表示恰好由若干段長度為 $p$ 的相同數字拼接而成，則認為 $(b, p)$ 是一種整齊的表示方式。

形式化地，設 $n$ 的 $b$ 進位表示為 $d_{k-1}d_{k-2} \dots d_1d_0$，若存在正整數 $c$ 使得總位數 $k = cp$，並且對於所有的 $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$（十六進位表示為 $66CCFF$），則 $(16, 2)$ 是一種整齊的表示方式。

為了順利贏取入場門票，你需要回答小 T 和小 S 的問題：主會場的房間號一共存在多少種整齊的表示方式？

輸入格式

每個測試點中包含多組測試數據。輸入的第一行包含一個正整數 $T$ ($1 \le T \le 10^3$)，表示數據組數。對於每組測試數據：

• 第一行包含一個正整數 $n$ ($1 \le n \le 10^{12}$)，表示主會場的房間號。

保證所有測試數據中 $n$ 的和不超過 $10^{12}$。

輸出格式

對於每組測試數據，輸出一行一個非負整數，表示答案。

範例

輸入格式 1

10
1
2
115
1111
2233
3355
191970
6737151
102934760424
618111100000

輸出格式 1

0
0
2
4
5
5
24
9
17
144

說明

對於第三組測試數據，$115 = (55)_{22} = (11)_{114}$，因此所有整齊的表示方式分別為 $(22, 2), (114, 2)$。

對於第四組測試數據，所有整齊的表示方式分別為 $(10, 2), (10, 4), (100, 2), (1110, 2)$。