Number of Points Visible from the Origin

Consider integer lattice points (x, y) on the coordinate plane such that 0 <= x, y <= N. The origin (0, 0) is not counted.

A point (x, y) is visible from the origin if the line segment from the origin to (x, y) does not pass through any other integer lattice point. For example, (4, 2) is not visible from the origin because the segment from (0, 0) to (4, 2) passes through (2, 1).

Given a positive integer N, count how many points (x, y) are visible from the origin.

The first line contains the number of test cases C, where 1 <= C <= 1,000.

Each of the next C lines contains one test case. Each test case consists of one positive integer N, where 1 <= N <= 1,000.

For each test case, output the number of points (x, y) visible from the origin on its own line.