Watering the Flower Garden

The garden is a square grid with $10^6$ rows and $10^6$ columns. It holds $N$ flowers, and flower $i$ sits in row $r_i$, column $c_i$.

You place sprinklers in the garden. A sprinkler goes on any empty cell, meaning a cell with no flower, and from that cell it shoots four streams of water along the grid: up, right, down, and left.

Flowers have a special property. A flower that receives water from any direction shoots water from its own cell in the same four directions: up, right, down, and left. Vertical streams and horizontal streams run at different heights, so they pass through each other instead of colliding. A stream runs to the edge of the grid, and neither a flower nor another stream blocks it.

Find the smallest number of sprinklers that waters all $N$ flowers.

The first line holds the number of test cases $T$ ($1 \le T \le 20$). Each test case has this form.

1. The first line holds the number of flowers $N$ ($1 \le N \le 100000$).
2. The next $N$ lines hold the row and the column of one flower, $r_i$ and $c_i$ ($1 \le r_i, c_i \le 1000000$). No two flowers share a cell.

For each test case, print on its own line the smallest number of sprinklers that waters every flower.

The two pictures below show placements that use the smallest number of sprinklers.

The first example test case

The second example test case