Description

lily很喜欢一位PLMM，所以一直想找个机会向她表白，但是PLMM使用的语言很奇怪，一般的语言根本无法和她沟通，所以lily很想学会这种语言。但是人学习这种语言需要30年，太长了！而计算机去学习的话，只要3个月，太快了！于是lily就赶紧学习计算机。 这类语言是用小立方体来表示的，即一些小立方体所围成的空间就是字的一部分，就象汉字里的“撇”，“捺”一样。现在lily在学最基本的，但他在学习中又想到一个有趣的问题：如果给你一些小立方体，他们可以围成多少个空心的长方体呢？（小立方体的体长为1单位）

Input

第一行是一个整数t(1 ≤ t ≤ 20)代表数据的组数，每组数据以M开始，M表示小立方体的个数，接下来的第i行有三个整数xi,yi和zi（它们是大于等于1小于等于100的数），表示小立方体的中心坐标。

Output

每组数据输出一个整数，表示围成空心长方体的个数。

Sample

Input

2
26
1 1 1
1 2 1
1 3 1
2 1 1
2 2 1
2 3 1
3 1 1
3 2 1
3 3 1
1 1 2
1 2 2
1 3 2
2 1 2
2 3 2
3 1 2
3 2 2
3 3 2
1 1 3
1 2 3
1 3 3
2 1 3
2 2 3
2 3 3
3 1 3
3 2 3
3 3 3
7
1 1 1
1 1 2
1 2 1
1 2 2
2 1 1
2 1 2
2 2 1

Output

1
0

Source: Tehran2004 (modified by lily)