说明

时间限制：1 Sec 内存限制：256 MB 输入文件：matrix.in 输出文件：matrix.out

【定义】

一个三元组 $(a,b,c)$ 是凹凸三元组，如果 $a,b,c$ 两两不等并且 $b$ 是最大的或是最小的。

$3$ 阶正方凹凸矩阵指 $3$ 阶正方矩阵

$$ A = \begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix} $$

满足以下所有条件：

1. 矩阵的每一行：数列 $a_{r1}, a_{r2}, a_{r3}$（$r=1,2,3$）均为凹凸三元组；

2. 矩阵的每一列：数列 $a_{1c}, a_{2c}, a_{3c}$（$c=1,2,3$）均为凹凸三元组；

3. 矩阵的反对角线：数列 $a_{13}, a_{22}, a_{31}$ 为凹凸三元组；

4. 矩阵的主对角线：数列 $a_{11}, a_{22}, a_{33}$ 为凹凸三元组。

简言之，矩阵的行、列、两条对角线对应的 $3$ 元素数列都必须是凹凸三元组。

【问题描述】

小明想把 $9$ 根木棍放入 $3 \times 3$ 的框架中，使木棍长度构成凹凸矩阵。目前他已经放好了 $7$ 根，还缺 $2$ 根。于是他从树林砍了一根长度为 $L$ 的木棍，需要将这根木棍分成两段（分割后两段长度均为正整数，且两段长度之和为 $L$），把这两段填入框架的空缺位置，使矩阵成为凹凸矩阵。

请你计算：有多少种不同的凹凸矩阵可以通过这种方式构成？

输入格式

1. 第一行：测试用例数量 $T$；

2. 每个测试用例：

   - 第一行：砍来的木棍长度 $L$；

   - 接下来 $3$ 行：每行 $3$ 个整数，表示 $3 \times 3$ 框架中已放置的木棍长度；其中 $a_{ij}=0$ 表示该位置未放置木棍（保证未放置的位置恰好有 $2$ 个）。

输出格式

对每个测试用例，输出一行整数，表示能构成的凹凸矩阵的数量。

样例

样例 1

1
10
7 8 5
1 9 0
3 0 2

1

样例说明：

仅 $a_{23}=6$、$a_{32}=4$ 这一种情况符合要求。

样例 2

1
10
1 3 0
5 0 7
4 8 6

0

样例说明：

无论如何分割木棍，都无法构成凹凸矩阵。

样例 3

4
3
4 0 8
6 9 2
5 0 7
10
0 1 1
0 1 1
1 1 1
6
1 5 4
0 10 1
3 1 0
38
20 16 17
0 12 14
19 14 0

2
0
1
6

样例说明：

第一个测试用例有两种合法情况：$a_{12}=1、a_{32}=2$ 或 $a_{12}=2、a_{32}=1$。

数据范围

对于 20% 的数据，$L \le 100$。

另有 20% 的数据，$a_{ij} \le 100$。

对于 100% 的数据，$1 \leq T \leq 100$，$1 \leq L \leq 10^9$，$0 \le a_{ij} \le 10^9$，保证未放置的位置恰好有 $2$ 个。