래스터화된 직선
시간 제한1초메모리 제한1024 MB
정수 격자에서 (0,0)에서 (a,b)까지 잇는 선분이 한 점보다 많이 지나는 단위 정사각형을 검은 픽셀로 칠할 때, 검은 픽셀이 정확히 N개가 되는 순서쌍 (a,b)의 개수를 구한다.
문제
Tomas는 컴퓨터 그래픽스를 공부하는 학생이다. 그에게는 아주 쉬운 숙제가 하나 있다. 점 (0, 0)에서 점 (a, b)까지 선분을 그리는 프로그램을 만드는 것이다. 여기서 정수 a, b (a > 0, b > 0) 는 프로그램의 입력이다.
그는 다음과 같은 알고리즘을 사용한다. 평면을 1x1 정사각형으로 나눈다. 이 정사각형들이 픽셀이다. (0, 0)에서 (a, b)까지의 선분이 어떤 정사각형과 두 점 이상에서 만나면 그 정사각형(픽셀)은 검은색이 된다. 그렇지 않으면 흰색이 된다. 다음 예를 보자.
입력
입력의 첫째 줄에는 테스트 케이스의 수를 나타내는 정수 T가 주어진다. 각 테스트 케이스 앞에는 빈 줄이 하나 있다.
각 테스트 케이스는 다음과 같다. 한 줄에 양의 정수 N이 하나 주어진다. N의 약수는 많아야 47개라고 가정할 수 있다.
출력
각 테스트 케이스마다 검은 픽셀을 정확히 N개 사용하는 선분의 개수를 한 줄에 하나씩 출력한다.
제한
- 1 ≤ T ≤ 60