← 返回题目列表

Codeforces · 2215/B

B. 重复

中文机器翻译题面 查看原题

作为11月11日(或11/11)出生的女孩,SS喜欢重复。例如,她最喜欢的英语单词是 b奥基每,她最喜欢的字母是 W(双 u、双 vé,或者无论你怎么称呼它),她最喜欢的动物是猫(kitten!) 和 rabb它(bunny!),她最喜欢的编程语言是 C++,她最喜欢的解析器是 LL(1),她最喜欢的优化算法是分支定界(BB),她最喜欢的单位是毫米(mm),她最喜欢的游戏是 LLLL,她在麻将中最喜欢的获胜牌是七对。她计划很快推出新歌《Silent-night Satellite》和《Siesta Stella》,所以她想选一首“预tty”号来装饰她的新歌封面。

SS从更高的角度观察这个世界,这意味着她从二进制数字系统开始,同时考虑所有标准位置数字系统中的整数。然后 SS 调用一个正整数 $$$n$$$ $$$(b, p)$$$-整洁 ($$$b,p\ge 2$$$)当且仅当:

  • 在 base-$$$b$$$ 表示中,对于某些正整数 $$$k$$$ 和整数 $$$0\le d_i \lt b$$$,$$$n$$$ 表示为 $$$\overline{d_{k\cdot p-1} d_{k\cdot p-2}\ldots d_1 d_0}$$$,这样对于每个$$$0\le i \lt k$$$,$$$d_{i\cdot p}=d_{i\cdot p+1}=\cdots=d_{(i+1)\cdot p-1}$$$。

例如,$$$2233$$$ 和 $$$3355$$$ 是 $$$(10,2)$$$-整洁, $$$1111$$$ 都是 $$$(10,2)$$$-整洁 和 $$$(10,4)$$$-整洁,$$$6\,737\,151=(66\textrm{CCFF})_{16}$$$ 是 $$$(16,2)$$$-整洁。此外,SS 定义了 整洁 正整数 $$$n$$$ 作为有序对 $$$(b, p)$$$ 的数量,使得 $$$n$$$ 为 $$$(b, p)$$$-整洁.

SS 给了你一个整数$$$n$$$。你的任务是确定 整洁 $$$n$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$1\le n\le 10^{12}$$$) — SS 给你的整数。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^{12}$$$。

输出

对于每个测试用例,输出一个整数 - 整洁 $$$n$$$。

示例

输入
复制

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}$$$。因此,$$$115$$$ 的整洁度是$$$2$$$。

在第四个测试用例中,$$$1111$$$ 是 $$$(10, 2)$$$-整洁, $$$(10, 4)$$$-整洁, $$$(100, 2)$$$-整洁和 $$$(1110, 2)$$$-整洁.