CF1267K.Key Storage

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 50000$），表示需要检查的常用密钥数量。接下来的 $t$ 行，每行包含一个整数 $k_i$（$1 \le k_i \le 10^{18}$），表示一个密钥。

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

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

由 ChatGPT 4.1 翻译