Problem G
Sneaky Snowninjas

The honourable ninja Hattori Hanzō has just conducted a successful assassination of one of the greatest enemies of his clan and needs to make sneaky getaway. Unfortunately for him, it has snowed recently and he needs to be careful not to leave any prints in the snow to avoid being tracked. He comes up with the brilliant plan of only stepping in the old footprints that already exist in the snow, so that his enemies can’t track him by his very distinctive shoe tracks (in hindsight, it was a mistake to get custom made shoes with the print “Hattori Hanzō” on the bottom).

Hattori Hanzō starts at coordinate $0$ / $0$ and must try to get as far away from that point as possible. Standing in one footprint, he can reach any other footprint where the distance is less than or equal to $100$ cm away.

Input

The first line of the input consist of a single integer $T$, the number of test cases.
Each of the following $T$ cases begins with a line consisting of one integer $N$, indicating the number of footprints in the snow, followed by $N$ lines, each containing two integers $X$ and $Y$, indicating the $x$ and $y$ coordinate of a given footprint in centimeters.

The limits on the input are:

• $1 \leq T \leq 20$

• $0 \leq N \leq 700\, 000$

• $-30\, 000 \leq X \leq 30\, 000$

• $-30\, 000 \leq Y \leq 30\, 000$

• The sum of all values of $N$ is at most $10^6$.

Output

For each test case, output the furthest distance (as the bird flies) the ninja can get from his starting point, rounded down to the nearest integer. Output this distance in centimeters.

1
5
50 50
50 150
150 50
225 50
50 240

245