Rikka와 방정식

힐베르트의 열 번째 문제의 결론에 따르면, 임의의 연립 방정식의 정수해를 모두 찾는 알고리즘은 만들 수 없다. 하지만 몇몇 간단한 방정식은 여전히 쉽게 풀 수 있다.

예를 들어, 정수 $x$, $y$가 $x^2 + y^2 = a$와 $xy = b$를 동시에 만족하는 경우가 있는지 어떻게 확인할까? $x + y = \pm \sqrt{a + 2b}$와 $x - y = \pm \sqrt{a - 2b}$를 계산한 뒤, $x$와 $y$가 모두 정수가 될 수 있는지 확인하면 된다.

Rikka는 이 문제가 너무 단순하다고 생각해서 더 어렵게 만들고 싶어 한다. Rikka는 등식을 $m$으로 나눈 나머지로 보면 문제가 달라질 때가 있다는 것을 안다. 그래서 이 문제에도 같은 방법을 적용하려 한다.

$0 \leq a, b < m$인 튜플 $(a, b, m)$은, $x^2 + y^2 \equiv a \pmod{m}$이고 $xy \equiv b \pmod{m}$을 만족하는 정수 $x$, $y$가 존재하는 경우에만 유효하다고 한다. 양의 정수 $n$이 주어지면, $m \leq n$인 유효한 튜플 $(a, b, m)$의 개수를 구하라. 개수가 매우 클 수 있으므로 $998\,244\,353$으로 나눈 나머지를 출력한다.

첫째 줄에 테스트 케이스의 개수 $t$ ($1 \leq t \leq 10^5$)가 주어진다. 각 테스트 케이스는 한 줄에 정수 $n$ ($1 \leq n \leq 10^7$) 하나로 주어진다.

각 테스트 케이스마다 유효한 튜플의 개수를 $998\,244\,353$으로 나눈 나머지를 한 줄에 출력한다.