题目背景

来自 2026 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2026）决赛。

题解等资源可在 https://github.com/dapingguo8/THUPC2026-final 查看。

为了庆祝 THUPC 十周年，小 T 和小 S 正在筹备一场盛大的十周年庆典！

庆典的首要准备工作是确定主会场。他们选定了一个房间作为主会场，并用森林墙纸、硕大无朋的大蒜玩偶、双"囍"壁挂（今年恰好也是清华 $(55)_{22}$ 周年校庆）和羽毛摆件把它装饰得整整齐齐。然而，兢兢业业的小 T 发现了一个棘手的问题------赫然挂在主会场前的门牌上的房间号看起来不够整齐。小 S 弱弱地提出，可以通过转换进制的方式，让房间号变得整齐。在尝试的过程中，他们发现能让房间号达到整齐效果的进制转换方案远不止一种。于是，小 T 和小 S 决定将这个有趣的房间号设计过程作为庆典的入场挑战，交由前来参会的大家解答。

题目描述

小 T 和小 S 确定的主会场房间号在十进制下为 $n$。小 T 对整齐的房间号表示方式给出了如下定义：对于正整数 $b, p \ge 2$，若房间号 $n$ 的 $b$ 进制表示恰好由若干段长度为 $p$ 的相同数字拼接而成，则认为 $(b, p)$ 是一种整齐的表示方式。

形式化地，设 $n$ 的 $b$ 进制表示为 $\overline{d_{k - 1} d_{k - 2} \dots d_1 d_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$（十六进制表示为 $\mathrm{66CCFF}$），则 $(16, 2)$ 是一种整齐的表示方式。

为了顺利赢取入场门票，你需要回答小 T 和小 S 的问题：主会场的房间号一共存在多少种整齐的表示方式？

输入格式

每个测试点中包含多组测试数据。输入的第一行包含一个正整数 $T \ (1 \le T \le 10 ^ 3)$，表示数据组数。对于每组测试数据：

• 第一行包含一个正整数 $n \ (1 \le n \le 10 ^ {12})$，表示主会场的房间号。

保证所有测试数据中 $n$ 的和不超过 $10 ^ {12}$。

输出格式

对于每组测试数据，输出一行一个非负整数，表示答案。

10
1
2
115
1111
2233
3355
191970
6737151
102934760424
618111100000

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)$。