Problem Description

比特游戏公司最近发布了一款新游戏《超维攻坚》。超维攻坚战是该游戏的最终BOSS战，$n$ 名玩家组成攻坚队对外宇宙的强大存在进行讨伐。所有玩家可以看作一个个三维空间内的质点，其中第 $i$ 个玩家的坐标是 $(x_i,y_i,z_i)$。

外宇宙的强大存在发动了它的大招：首先它控制住了所有玩家，使得所有玩家被固定在原位置不能移动；此外由于它是超维生物，因此它的每次攻击投射到三维可以视作选定实数 $a,b,c,d$，并秒杀所有满足 $ax+by+cz+d\geq 0$ 的玩家。外宇宙的强大存在可以进行任意多次攻击，但每次攻击不一定会瞄准玩家。

BOSS大招演出完毕后，已知幸存了至少一名玩家，请问有多少种可能的局面？两个局面被认为不同当且仅当存在一名玩家在一个局面中幸存，却在另一个局面中阵亡。

Input

第一行包含一个正整数 $T$ ($1\leq T\leq 10$)，表示测试数据的组数。

每组数据第一行包含一个正整数 $n$ ($1\leq n\leq 15$)，表示攻坚队中玩家的数量。

接下来 $n$ 行，每行三个整数 $x_i,y_i,z_i$ ($0\leq x_i,y_i,z_i\leq 100$)，依次表示每个玩家的坐标。输入数据保证玩家所处的坐标两两不同。

Output

对于每组数据输出一行一个整数，即大招演出完毕后可能的局面数量。

1
5
0 0 0
4 0 0
2 4 0
2 2 5
2 2 1

30