시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 540 253 200 49.383%

문제

(0,0)에서 보이는 (x,y)의 개수를 구하려고 한다.(x,y >= 0, 정수)

(0,0)에서 (x,y)가 보이려면 (0,0)과 (x,y)를 연결하는 직선이 다른 점을 통과하지 않아야 한다. 예를 들어 (4,2)는 (0,0)에서 보이지 않는다. 그 이유는 (0,0)과 (4,2)를 연결하는 직선이 (2,1)을 통과하기 때문이다. 아래 그림은 0 <= x,y<=5인 경우에 (0,0)에서 보이는 점의 개수이다. 단, (0,0)은 계산하지 않는다.

N이 주어졌을 때, 원점에서 보이는 (x,y) 좌표의 개수를 출력하시오. (0 <= x,y <= N)

입력

첫째 줄에 테스트 케이스의 개수 C(1<=C<=1,000)가 주어진다. 각 테스트 케이스는 자연수 N(1<=N<=1,000) 하나로 이루어져 있고, 한 줄에 하나씩 주어진다.

출력

각 테스트 케이스에 대해 한 줄에 하나씩 (0,0)에서 보이는 점(x,y)의 개수를 출력한다.

예제 입력 1

4
2
4
5
231

예제 출력 1

5
13
21
32549
W3sicHJvYmxlbV9pZCI6IjI3MjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjZjRcdWM3NzRcdWIyOTQgXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCIsImRlc2NyaXB0aW9uIjoiPHA+XHJcblx0KDAsMClcdWM1ZDBcdWMxMWMgXHViY2Y0XHVjNzc0XHViMjk0ICh4LHkpXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0Lih4LHkgJmd0Oz0gMCwgXHVjODE1XHVjMjE4KTxcL3A+XHJcblxyXG48cD5cclxuXHQoMCwwKVx1YzVkMFx1YzExYyAoeCx5KVx1YWMwMCBcdWJjZjRcdWM3NzRcdWI4MjRcdWJhNzQgKDAsMClcdWFjZmMgKHgseSlcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YzljMVx1YzEyMFx1Yzc3NCBcdWIyZTRcdWI5NzggXHVjODEwXHVjNzQ0IFx1ZDFiNVx1YWNmY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0ICg0LDIpXHViMjk0ICgwLDApXHVjNWQwXHVjMTFjIFx1YmNmNFx1Yzc3NFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YWRmOCBcdWM3NzRcdWM3MjBcdWIyOTQgKDAsMClcdWFjZmMgKDQsMilcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YzljMVx1YzEyMFx1Yzc3NCAoMiwxKVx1Yzc0NCBcdWQxYjVcdWFjZmNcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LiBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNzQwIDAgJmx0Oz0geCx5Jmx0Oz01XHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMCAoMCwwKVx1YzVkMFx1YzExYyBcdWJjZjRcdWM3NzRcdWIyOTQgXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc3NFx1YjJlNC4gXHViMmU4LCAoMCwwKVx1Yzc0MCBcdWFjYzRcdWMwYjBcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3Fxd3EucG5nXCIgc3R5bGU9XCJ3aWR0aDogMjIxcHg7IGhlaWdodDogMjA4cHg7IFwiIFwvPjxcL3A+XHJcblxyXG48cD5cclxuXHROXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzZkMFx1YzgxMFx1YzVkMFx1YzExYyBcdWJjZjRcdWM3NzRcdWIyOTQgKHgseSkgXHVjODhjXHVkNDVjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWMyZGNcdWM2MjQuICgwICZsdDs9IHgseSAmbHQ7PSBOKTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBDKDEmbHQ7PUMmbHQ7PTEsMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1Yzc5MFx1YzVmMFx1YzIxOCBOKDEmbHQ7PU4mbHQ7PTEsMDAwKSBcdWQ1NThcdWIwOThcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSAoMCwwKVx1YzVkMFx1YzExYyBcdWJjZjRcdWM3NzRcdWIyOTQgXHVjODEwKHgseSlcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNzI1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVmlzaWJsZSBMYXR0aWNlIFBvaW50cyIsImRlc2NyaXB0aW9uIjoiPHA+QSBsYXR0aWNlIHBvaW50ICh4LCB5KSBpbiB0aGUgZmlyc3QgcXVhZHJhbnQgKHggYW5kIHkgYXJlIGludGVnZXJzIGdyZWF0ZXIgdGhhbiBvciBlcXVhbCB0byAwKSwgb3RoZXIgdGhhbiB0aGUgb3JpZ2luLCBpcyB2aXNpYmxlIGZyb20gdGhlIG9yaWdpbiBpZiB0aGUgbGluZSBmcm9tICgwLCAwKSB0byAoeCwgeSkgZG9lcyBub3QgcGFzcyB0aHJvdWdoIGFueSBvdGhlciBsYXR0aWNlIHBvaW50LiBGb3IgZXhhbXBsZSwgdGhlIHBvaW50ICg0LCAyKSBpcyBub3QgdmlzaWJsZSBzaW5jZSB0aGUgbGluZSBmcm9tIHRoZSBvcmlnaW4gcGFzc2VzIHRocm91Z2ggKDIsIDEpLiBUaGUgZmlndXJlIGJlbG93IHNob3dzIHRoZSBwb2ludHMgKHgsIHkpIHdpdGggMCAmbGU7IHgsIHkgJmxlOyA1IHdpdGggbGluZXMgZnJvbSB0aGUgb3JpZ2luIHRvIHRoZSB2aXNpYmxlIHBvaW50cy48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9xcXdxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIwOHB4OyBvcGFjaXR5OjAuOTsgd2lkdGg6MjIxcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHdoaWNoLCBnaXZlbiBhIHZhbHVlIGZvciB0aGUgc2l6ZSwgTiwgY29tcHV0ZXMgdGhlIG51bWJlciBvZiB2aXNpYmxlIHBvaW50cyAoeCx5KSB3aXRoIDAgJmxlOyB4LCB5ICZsZTsgTi4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgQywgKDEgJmxlOyBDICZsZTsgMTAwMCkgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBkYXRhc2V0cyB0aGF0IGZvbGxvdy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBkYXRhc2V0IGNvbnNpc3RzIG9mIGEgc2luZ2xlIGxpbmUgb2YgaW5wdXQgY29udGFpbmluZyBhIHNpbmdsZSBpbnRlZ2VyIE4sICgxICZsZTsgTiAmbGU7IDEwMDApLCB3aGljaCBpcyB0aGUgc2l6ZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhc2V0LCB0aGVyZSBpcyB0byBiZSBvbmUgbGluZSBvZiBvdXRwdXQgY29uc2lzdGluZyBvZjogdGhlIGRhdGFzZXQgbnVtYmVyIHN0YXJ0aW5nIGF0IDEsIGEgc2luZ2xlIHNwYWNlLCB0aGUgc2l6ZSwgYSBzaW5nbGUgc3BhY2UgYW5kIHRoZSBudW1iZXIgb2YgdmlzaWJsZSBwb2ludHMgZm9yIHRoYXQgc2l6ZS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=