题目内容

小塔最近热衷于数独游戏。在厌倦了传统数独后，他想到一个有趣的规则:有$3x3$的方格，他要把$1$~$9$的这$9$ 个数字不重不漏地填入这9个方格，并且保证填入的每个数字周围没有临近数。例如在中间位置填了数字$4$， 那么数字$3$和$5$不能出现在数字$4$上下左右四个位置中任何一个。

现在小塔已经填上了几个数字，他想知道一共有多少种符合上述规则的填充方案。当且仅当至少存在一个位置

在这两种方案中填充的数字不同时，两种填充方案被认为是不同的。

输入描述

第一行$1$个整数$T$,表示数据组数。

对每组数据，有三行，每行三个整数。这三行三列中的第$i$行第$j$列的数a代表题面描述中的$3x3$方格对应位置的情况。如果$a=0$表示那个格子还未填充;如果是一个[$1,9$]范围内的整数表示小明已填好的数字。保证至少有一个格子未填充，已填充的格子不会出现重复数字，但有可能不合法。 $1≤T≤100$，其中$0≤a_{ij}≤9$

输出描述

对于每组数据，输出一行一个整数表示答案，即合法的填充方案数，使得最终结果中任何一个位置上下左右相邻的数(如果有的话)与该位置的数绝对值之差不为$1$，且不重不漏用完$1$~$9$这$9$个数字。形式化地，要求对任意位置$i,j$满足$a_{{(i-1)}j}$,$a_{{(i+1)}j}$,$a_{i{(j-1)}}$,$a_{i{(j+1)}}$(如果存在)与$a_{ij}$的绝对值之差不为$1$，且不重不漏使用完$9$个数字。 如果没有任何可行的方案，输出$0$。

样例1

输入

2
1 8 5
4 6 3
0 2 0
1 3 5
2 6 8
2 7 0

输出

2
0

说明

对第一组数据，有两种填法，第一种为

$1\ 8\ 5$

$4\ 6\ 3$

$7\ 2\ 9$

第二种为

$1\ 8\ 5$

$4\ 6\ 3$

$9\ 2\ 7$ 如此，没有任何一个方格与相邻的方格绝对值之差为$1$。

对第二组数据，只有唯一(不合法的)填法: $1\ 3\ 5$ $4\ 6\ 8$ $2\ 7\ 9$

其中数字$9$与其上的数字$8$绝对值之差为$1$，不合条件。

因此合法方案数为$0$。