为什么 YahAHa 总是喜欢立方体？

YahAHa 有一个特殊的立方体。立方体的每个面上都有一个数字 $x$ ($1 \le x \le 1000$)。起初，YahAHa 将立方体放在桌子上。然后将立方体滚动了 $n$ ($1 \le n \le 2 \times 10^5$) 次，每次沿着底面的某一条边滚动。这意味着将顶面旋转到其他面。

YahAHa 有一个数字 $x$，初始值为 $1$。每次滚动后，YahAHa 将立方体正面的数字乘以 $x$。乘积非常大，因此 YahAHa 记录了乘积对 $998244353$ 取模的结果。

粗心大意的是，YahAHa 忘记了其中 $m$ ($1 \le m \le 20$) 次滚动的方向。但 YahAHa 记录了立方体的初始状态、最终状态以及滚动后正面数字乘积对 $998244353$ 取模的结果。

你能告诉 YahAHa 有多少种满足所有条件的滚动方式吗？

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 ($1 \le T \le 10$)。接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 2 \times 10^5$)，表示立方体滚动的次数。

下一行包含 $n$ 个整数。第 $i$ 个整数表示第 $i$ 次滚动。$a_i = 1$ 表示将顶面旋转到前方；$a_i = 2$ 表示将顶面旋转到后方；$a_i = 3$ 表示将顶面旋转到左方；$a_i = 4$ 表示将顶面旋转到右方；$a_i = 0$ 表示 YahAHa 忘记了这次滚动的方向。

下一行包含 $6$ 个不同的整数，表示立方体的初始状态。

下一行包含 $6$ 个不同的整数，表示立方体的最终状态。

立方体的状态由 $6$ 个整数表示。这 $6$ 个整数按前、后、左、右、上、下侧的顺序排列。

最后一行包含一个整数，表示正面数字乘积对 $998244353$ 取模的结果。

保证满足 $n \ge 10^5, m \ge 20$ 的测试用例最多有 $5$ 个。

输出格式

对于每个测试用例： 输出一行，包含一个整数，表示答案。

样例

输入 1

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

输出 1

1

说明

样例的旋转方向：3 4 4 2 1 4 4 正面数字的变化：1->1->1->1->3->1->1->1 展开图：