Description

Karl 正在开发一个密钥存储服务。每个用户都有一个正整数密钥。

Karl 知道明文存储密钥是不安全的做法。因此，他决定不直接存储密钥，而是存储密钥的指纹。不过他觉得使用现有的指纹算法太无聊了，于是自己发明了一种新的算法。

Karl 的指纹算法计算过程如下：

1. 将给定的整数除以 2（整数除法）
2. 将结果除以 3
3. 继续除以 4
4. 依此类推，直到结果为 0 指纹定义为这些除法运算产生的余数组成的多重集。

例如，对密钥 11 应用该算法：

• 11 ÷ 2 = 5 余 1
• 5 ÷ 3 = 1 余 2
• 1 ÷ 4 = 0 余 1 因此密钥 11 产生的余数序列是 $[1, 2, 1]$，指纹多重集为 $\{1, 1, 2\}$。

Ksenia 想证明 Karl 的指纹算法并不完善。例如她发现密钥 178800 和 123456 都会产生相同的指纹 $\{0, 0, 0, 0, 2, 3, 3, 4\}$。这意味着像 123456 这样常用且容易猜测的密钥可能会与其他密钥产生指纹冲突。

Ksenia 想用更有说服力的数据来证明这一点。她需要计算与给定常用密钥列表中的密钥具有相同指纹的其他密钥数量。你的任务就是帮助她完成这个计算。

Input Format

第一行包含一个整数 $t$（$1 \le t \le 50\,000$）—— 需要检查的常用密钥数量。 接下来的 $t$ 行，每行包含一个整数 $k_i$（$1 \le k_i \le 10^{18}$）—— 密钥值。

Output Format

对于每个密钥，输出一个整数 —— 与该密钥具有相同指纹的其他密钥数量。

3
1
11
123456

0
1
127

Hint

与密钥 11 具有相同指纹的另一个密钥是 15。15 产生的余数序列是 $[1, 1, 2]$，因此这两个密钥的指纹多重集都是 $\{1, 1, 2\}$。

翻译由 DeepSeek V3 完成