J. Hot Pepper
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Red Dragon Dew has recently become obsessed with Plants vs. Zombies Fusion Edition (by the Lan Piaopiao team). Like the original Plants vs. Zombies, there is a plant called the Hot Pepper, which can damage all zombies in a row simultaneously. Based on this, Dew came up with a problem:

On an infinite two-dimensional grid, each cell can hold at most one pepper. There are two types of peppers: one that explodes vertically (parallel to the y-axis) and one that explodes horizontally (parallel to the x-axis). Now, there are already $$$k$$$ peppers with fixed types on the grid, and Dew wants to know the minimum number of additional peppers that need to be placed so that every pepper is burned by at least one other pepper.

Formally, given a set of triples $$$S=\{(x,y,w)\}$$$, where $$$(x,y,w)\in U$$$ and $$$U=N\times N\times \{0,1\}$$$, the problem asks for the minimum number of additional elements $$$(x,y,w)\in U$$$ to be added to $$$S$$$ such that for every $$$(x_0,y_0,w_0)\in S$$$, there exists either an element $$$(x_0,y',0) \in S,y'\not=y_0$$$ or an element $$$(x',y_0,1)\in S,x'\not=x_0$$$. Meanwhile, the set must satisfy that for any two elements $$$(x_1,y_1,w_1)$$$ and $$$(x_2,y_2,w_2)$$$ in $$$S$$$, it is not the case that both $$$x_1=x_2$$$ and $$$y_1=y_2$$$ simultaneously.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ $$$(1\le T\le 50000)$$$. The description of the test cases follows. The first line of each test case contains an integer $$$k$$$ ($$$1\le k\le 2\times 10^5$$$), which represents the number of peppers.

The next $$$k$$$ lines, each line contains 3 integers $$$x,y,w$$$ ($$$1\le x,y\le 10^9, w\in\{0,1\}$$$), representing the position and type of each pepper, with the guarantee that no two peppers share the same position.

For all test cases, it is guaranteed that $$$\sum k\le 2\times 10^5$$$.

Output

For each test case, output the minimum number of additional peppers required.

Examples
Input
3
4
1 1 1
1 2 1
1 3 1
2 3 1
3
1 1 0
2 1 0
2 2 1
6
1 3 0
2 3 1
2 2 0
3 2 1
3 1 0
1 1 1
Output
2
2
0
Input
3
3
1 1 0
2 1 0
3 2 1
4
1 1 0
2 1 0
3 2 1
3 3 1
2
1 1 0
2 2 1
Output
3
3
2
Note

Here is the first test case for example 1, assume the lower left corner is (1,1), dark arrows are the peppers original, and two light arrows are one possible minimum peppers added scheme.