문제
2차원 평면에서 정수 좌표 (x, y)위치에 있는 점이 (0, 0)에서 보인다는 것은 (0, 0)에서 (x, y)까지 직선을 그었을 때, 이 두개의 정수 좌표를 제외한 다른 정수 좌표를 거치지 않는다는 것이다.
(0, 0) 부터 (N, N)의 정수 좌표들에 대해 (0, 0)에서 보이는 정수좌표가 총 몇 가지인지 알아내는 프로그램을 작성하라.
아래 그림의 경우는 N = 5의 경우에 보이는 점들을 (0, 0)과 이은 예이다.
입력
입력의 첫 번째 줄에는 테스트 케이스의 개수 T(0< T <=10000) 가 입력된다. 각 테스트 케이스는 한 줄로 이뤄지며 10,000 이하의 자연수 N 이 입력된다.
출력
각 테스트 케이스에 대해 보이는 점의 개수를 한 줄에 출력한다.
예제
4
2
4
5
231
5
13
21
32549
태그
출처
Greater New York 2006, poj 3090
로그인해야 코드를 작성할 수 있어요.