Surveillance System

To protect the leopard of the snow covered Kilimanjaro, which is close to extinction, an international agency designated the area within 50 km of the summit of Mount Kilimanjaro as a nature reserve. The agency also built a surveillance system of closed circuit cameras to keep people out of the reserve. The system was built so that at least one camera watches every sector, and enough spare cameras run in case a camera breaks. Cameras broke far less often than expected, so the government now wants to cut maintenance costs by running fewer cameras whose ranges overlap.

The cameras sit along the boundary of the reserve, a circle of radius 50 km, and watch for people crossing it. Each camera has its own range, depending on where it is installed. The northernmost point of the boundary is sector 1, and the boundary continues clockwise as sectors 2, 3, …, 100000. Sector 100000 is followed by sector 1 again. Each camera starts at one sector and watches several consecutive sectors clockwise from there. Given the range of every camera, find the smallest number of cameras that still leaves every sector watched by at least one camera. Assume that no test case is given without an answer.

In the picture above, each arc is the range of one camera. Running only the cameras drawn in red is enough to watch every sector.

Input arrives on standard input. The first line has the number of test cases $T$ ($1 \le T \le 20$). The first line of each test case has the number of installed cameras $K$ ($1 \le K \le 20000$). Each of the next $K$ lines describes the range of one camera with two positive integers $p$ and $r$ ($1 \le p, r \le 100000$), which mean the $r$ consecutive sectors that start at sector $p$ and run clockwise. The numbers are separated by whitespace.

Print to standard output. For each test case print the smallest number of cameras that watch every sector, one per line.