众所周知，一个 $3 \times 3$ 的幻方必须满足以下两个条件： 1. 九个数字必须均为正整数且互不相同。 2. 所有行、列以及对角线的数字之和相等。

除了 Matt Parker$^1$ 之外，大家都知道这一点。他想要创建一个“平方幻方”，即一个同时满足第三个条件的幻方： 3. 每个数字都是一个正整数的平方。

他的“成果”可以在角落的图片中看到。正如你所注意到的，他的方阵并没有那么“幻”……不仅大多数数值出现了两次，而且还有一条对角线的和是错误的。老实说，除了包含非平方数之外，这个方阵几乎没有什么更糟糕的地方了。好吧，至少他尝试过了！

但那已是过去式。在发现 Parker Square 之后，他决定彻底忽略第 3 条性质，转而给第 2 条性质赋予一个新的变化。他现在考虑的是“乘法幻方”，它与普通幻方完全一样，只是所有行、列和对角线的乘积必须相等，而不是和相等。谁知道呢，说不定 Matt 未来真的能找到一个真正的乘法幻方！

有了这个定义，Matt 写了一些糟糕的 Python 代码——这是他的原话，不是我们的——用来计算乘法幻方 $3 \times 3$ 方阵的数量，要求其中每一行、每一列或每一条对角线的乘积最多为 $n$。正如你现在可能已经猜到的，他的代码太慢了。因此，我们要求你做同样的事情，但要更高效。给定一个整数 $n$，计算乘积最多为 $n$ 的乘法幻方 $3 \times 3$ 方阵的数量。

The Parker Square. © Brady Haran, used with permission

输入格式

输入包含： 一行包含一个整数 $t$ ($1 \le t \le 10^5$)，表示测试用例的数量。 $t$ 行，每行包含一个整数 $n$ ($1 \le n \le 10^{18}$)，表示最大乘积。

输出格式

对于每个测试用例，输出乘积最多为 $n$ 的乘法幻方数量。

样例

样例输入 1

3
500
1000
3000

样例输出 1

8
16
56

$^1$ 娱乐数学家、作家、喜剧演员、YouTube 网红及科学传播者。