시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)71325018641.060%

문제

피타고라스 정리는 다음과 같다.

직각삼각형의 빗변의 길이가 $c$, 나머지 두 변의 길이가 각각 $a$, $b$라 할 때, $a^2+b^2=c^2$을 만족한다.

피타고라스 정리의 증명은 따로 책이 있을 정도로 다양한 방법이 있다. 현민이는 이 증명법 중 근본은 피타고라스가 했다고 알려진 아래 방법이라고 주장한다.

옆에서 이를 듣던 민재는 피타고라스에 푹 빠진 현민이를 구출하기 위해 다음과 같이 물어봤다.

“위 그림에서 $a$, $b$가 $N$ 이하의 양의 정수이면서, 노란색 정사각형의 넓이가 파란색 삼각형 하나 넓이의 정수배가 되려면 어떤 조건을 만족해야 해?”

현민이를 도와 답을 찾아 피타고라스로부터 구출해 주자.

입력

첫 번째 줄에 테스트 케이스의 개수 $T(1\le T\le 10^6)$가 주어진다.

두 번째 줄부터 $T$줄에 걸쳐 각 테스트 케이스 별 $N(1\le N\le 10^{18})$이 한 줄에 한 개씩 주어진다.

출력

첫 번째 줄부터 $T$줄에 걸쳐 각 테스트 케이스 별로 조건을 만족하는 순서쌍 $\left( a,b \right)$의 개수를 한 줄에 한 개씩 출력한다.

서브태스크

번호배점제한
120

$N\le 5\, 000$; $T=1$

220

$N\le 5\, 000$

360

추가적인 제한 조건 없음

예제 입력 1

4
1
2
3
4

예제 출력 1

1
4
5
8

첫 번째 테스트 케이스의 경우 가능한 순서쌍은 $\left( 1,1 \right)$이다.

두 번째 테스트 케이스의 경우 가능한 순서쌍은 $\left( 1,1 \right)$, $\left( 1,2 \right)$, $\left( 2,1 \right)$, $\left( 2,2 \right)$이다.

세 번째 테스트 케이스의 경우 가능한 순서쌍은 $\left( 1,1 \right)$, $\left( 1,2 \right)$, $\left( 2,1 \right)$, $\left( 2,2 \right)$, $\left( 3,3 \right)$이다.

채점 및 기타 정보

  • 예제는 채점하지 않는다.