32897번 - It’s a Kind of Magic 다국어

문제

Everyone knows that a 3ドル\times3$ magic square must meet two criteria:

1. All nine numbers must be positive and distinct.
2. The sums along all rows, columns, and diagonals are equal.

Everyone, except maybe Matt Parker¹. He wants to create a magic square of squares, that is, a magic square that also meets a third criterion:

3. Each number is a square of a positive integer.

His "result" can be seen in the picture in the corner. As you may notice, his square is not that magic... Not only do most of the values appear twice, it also has a diagonal with the wrong sum. To be honest, apart from containing non-square values, there is not much that could make this square worse. Well, at least he tried!

But that is all in the past. After finding the Parker Square, he decided to completely ignore property 3ドル$ from now on and to instead give property 2ドル$ a new twist. He now considers multiplicative magic squares, which are exactly like normal magic squares except that the products along all rows, columns, and diagonals have to be equal, instead of the sums. Who knows, Matt might even manage to find a proper multiplicative magic square in the future!

With this definition at hand, Matt wrote some terrible Python code -- his words, not ours -- to count the number of multiplicative magic 3ドル\times 3$ squares where the product of the numbers in a single row, column, or diagonal is at most $n$. As you may have guessed by now, his code is way too slow. Therefore, we task you to do the same, just more efficiently. Given an integer $n,ドル count the number of multiplicative magic 3ドル\times 3$ squares with product at most $n$.

¹Recreational mathematician, author, comedian, YouTube personality, and science communicator.

입력

The input consists of:

• One line with an integer $t$ (1ドル \leq t \leq 10^5$), the number of test cases.
• $t$ lines, each with an integer $n$ (1ドル \leq n \leq 10^{18}$), the maximum product.

출력

For each test case, output the number of multiplicative magic squares with product at most $n$.

제한

힌트