As tension between Uchiha clan and rest of the village is increasing , Fourth Hokage of Leaf Village Minato decides to do something to solve this issue.
There are N house in village , some of them belong to Uchihas and rest to others .
As for now Uchihas live spreaded in village between other clans.
Minato thinks of separating both the clans by relocating some of houses and separating them with a straight wall.
For doing this , he may have to reshuffle some Uchiha as well non-Uchihas houses too. He wants as less houses to be disturbed.
You are a famous mathematician in village so he comes you for help . Help him to find minimum no of houses to be relocated to separate the Uchiha Clan .
It is assured that no three house are in straight line and all the houses are situated at integer co-ordinates .
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each testcase contains a positive integer N- the number of house in village
Next N line contains 3 integers x , y , val with (x,y) denoting the co-ordinate of point and value is the boolean value assigned to point .