Edges of that thing

Time Limit: 5 Seconds    Memory Limit: 65536 KB

Maybe you have heard about that problem where you have a set of nails on a board and you put a rubber band around them and release it, the rubber shrinks and get stuck on some nails. Then you want to find out something about the shape of that rubber band (like the set of nails that it is touching, size of band, etc).

But that's easy, so this problem ain't that nails on a board. Let's assume that instead of having a set of nails on a board, we have a set of fixed points in the air (I couldn't figure out how it works in real world, but feel free to imagine for yourself), and instead of a rubber band, we have a rubber ball, that is surrounding all these points. Now what happens if we release the ball? What would be the shape of it? In general it would form a polyhedron. Picturing that in mind, I was wondering for a specific set of points, how many edges that thing has! Therefore, your task is to answer my wonder.

Input

The input starts with an integer T, denoting the number of test cases.

Each test case starts with an integer n (8 <= n <= 100), which represents the number of points. Then comes n lines, each having three space-separated integers x, y and z, which are the coordinates of each point in the air.

Output

For each test case, output one integer, the number of edges on that thing!

Note: the first test case is a cube and the second test case is a pyramid with a square base (four edges in base and four edges connecting the top to the base).

Sample Input

2
10
0 0 0
2 0 0
2 2 0
0 2 0
0 0 2
2 0 2
2 2 2
0 2 2
1 1 1
1 2 1
8
0 0 0
4 0 0
4 4 0
0 4 0
2 2 0
2 2 1
2 2 2
2 2 4

Sample Output

12
8

Submit

Source: 13th Iran Nationwide Internet Contest - SBU