Karl 正在开发一项密钥存储服务。每个用户都有一个正整数密钥。
Karl 知道以纯文本形式存储密钥是不好的做法。因此,他决定不存储钥匙,而是存储钥匙的指纹。然而,使用一些现有的指纹算法对他来说太无聊了,所以他发明了自己的算法。
Karl 的指纹是通过以下过程计算的:将给定整数除以 2,然后将结果除以 3,然后将结果除以 4,依此类推,直到得到等于 0 的结果(我们每次都在谈论整数除法)。指纹被定义为这些除法的余数的多重集。
例如,Karl 的指纹算法应用于密钥 11:11 除以 2 得到余数 1 和结果 5,然后 5 除以 3 得到余数 2 和结果 1,1 除以 4 得到余数 1 和结果 0。因此,密钥 11 产生余数序列 $$$[1, 2, 1]$$$ 并具有指纹多重集$$$\{1, 1, 2\}$$$。
Ksenia想要证明Karl的指纹算法不是很好。例如,她发现密钥 178800 和 123456 都会产生 $$$\{0, 0, 0, 0, 2, 3, 3, 4\}$$$ 的指纹。因此,用户面临着与一些常用且容易猜测的按键(如 123456)发生指纹冲突的风险。
Ksenia 想让她的话更有说服力。她想要计算与给定的一些常用钥匙列表中的钥匙具有相同指纹的其他钥匙的数量。你的任务是帮助她。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 50\,000$$$) — 要检查的常用键的数量。接下来的 $$$t$$$ 行中的每一行都包含一个整数 $$$k_i$$$ ($$$1 \le k_i \le 10^{18}$$$) — 密钥本身。
输出
对于每个按键,打印一个整数 - 具有相同指纹的其他按键的数量。
示例
输入 #1
3 1 11 123456
输出 #1
0 1 127
注意
与 11 具有相同指纹的另一个密钥是 15。15 产生余数序列 $$$[1, 1, 2]$$$。所以这两个数字都有指纹多重集 $$$\{1, 1, 2\}$$$。