일종의 마법

누구나 알듯이 $3\times3$ 마방진은 다음 두 조건을 만족해야 한다:

1. 아홉 개의 수는 모두 양수이고 서로 달라야 한다.
2. 모든 행, 열, 대각선의 합이 같아야 한다.

모두가 그렇게 알고 있지만, 취미 수학자 Matt Parker¹는 예외일지도 모른다. 그는 여기에 세 번째 조건을 더한 제곱수 마방진을 만들고 싶어 한다.

3. 각 수는 양의 정수의 제곱이다.

귀퉁이의 그림이 그 결과물이다. 눈치챘겠지만 그의 정사각형은 그다지 마법 같지 않다. 대부분의 값이 두 번씩 나오고, 대각선 하나는 합이 틀린다. 제곱이 아닌 값을 포함하는 것 말고는 이보다 더 나빠질 여지가 거의 없다. 그래도 시도는 했다!

"Parker Square"를 찾은 뒤 그는 앞으로 세 번째 조건을 무시하기로 했다. 대신 두 번째 조건에 새로운 변형을 준다. 그가 생각하는 것은 곱셈 마방진이다. 합 대신 모든 행, 열, 대각선의 곱이 같아야 한다는 점을 빼면 일반 마방진과 똑같다. 언젠가 Matt가 제대로 된 곱셈 마방진을 찾아낼지도 모른다.

Matt는 행, 열, 대각선의 곱이 $n$ 이하인 곱셈 $3\times3$ 마방진의 개수를 세려고 끔찍한 파이썬 코드를 짰다(그의 표현이며 우리의 표현이 아니다). 이 코드는 너무 느리다. 같은 일을 더 효율적으로 하는 프로그램을 작성하라. 정수 $n$이 주어지면, 곱이 $n$ 이하인 곱셈 $3\times3$ 마방진의 개수를 구하라.

¹ 취미 수학자, 저자, 코미디언, 유튜버, 과학 커뮤니케이터.

입력은 다음과 같다.

첫 줄에 테스트 케이스의 수를 나타내는 정수 $t$ ($1 \leq t \leq 10^5$)가 주어진다.

이어서 $t$개의 줄에 각각 정수 $n$ ($1 \leq n \leq 10^{18}$)이 주어진다. 곱의 상한이다.

각 테스트 케이스마다 곱이 $n$ 이하인 곱셈 마방진의 개수를 한 줄에 출력한다.