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\}$。