题目描述

在遥远的 Utopia City 里，有一种美食让人们为之倾倒：披萨。披萨是一种做工非常讲究的美食，必须由 $n$ 种原料共同制作（饼皮，红肠，大虾，各种酱料，各种装饰，等等）。Utopia City 的主干道上有 $b$ 个商业园区，每个园区里都有一座 PizzaHut 大楼；在早先的青铜时代里，PizzaHut 的运营方式很简单，一楼是一个巨大的 PizzaHut 柜台，贩卖各种各样的 Pizza。在大楼的其他地方有恰好 $n$ 家原料商，每一家都供应 PizzaHut 的一种原料。

这样的日子持续了很多年。不知从黑铁时代的哪个年头开始，原料商们觉得售卖单一原料已经无利可图，因此所有的原料商都开始售卖所有的 $n$ 种原料做 Pizza。原料商们提供的原料良莠不齐，所幸可以用一个统一指标——质量来衡量。我们假设第 $i$ 个商业园区里第 $j$ 个原料商提供的第 $k$ 种原料的质量为 $q_{i,j,k}\ (1 \leq i \leq b,1 \leq j \leq n,1 \leq k \leq n)$。

问题又来了。一楼的 PizzaHut 柜台由于进货渠道混乱已经毫无消息，而虽然一家原料商能供应做 Pizza 的所有原料，但要在所有的 $b \times n$ 个原料店中找到一家在各种原料上都可圈可点的店面是十分困难的。国家的披萨工业陷入了困境。

所幸的是这个问题最终得到了解决：位于同一座大楼里的原料商们开始进行合作推广，贩售由两个原料商共同提供原料制作的 Pizza。人们发现两种来自不同商铺的相同原料混合将带来意想不到的效果，使得原先的美味上升了一大个层次。

具体地说，两种相同原料的混合将导致他们对应的质量进行相乘。因此，一个由第 $i$ 座大楼里第 $j1$ 和第 $j2$ 个商户联手制作的披萨，其质量是 $\sum\limits_{k=1}^{n} {q_{i,j1,k} \times q_{i,j2,k}}$。这也是这种披萨的最终定价。

Tarat 和 Ratar 通过一个偶然机会得到了 Utopia City 的限期居留权。虽然限期很长，但他们还是希望能抓紧时间，品尝城市里的美味披萨。在若干天后，他们尝遍了所有市场上售卖的 $\frac{b \times n \times (n-1)}{2}$ 种披萨。虽然在接下来去哪里吃披萨起了很大的争执，但是最终他们还是达成了一个共识：只在一个园区里吃披萨实在是太无聊了。

于是 Tarat 和 Ratar 找到了 Polaris，她是一个地下披萨商，经常在两个不同大楼的原料商里进原料做披萨。和上面的公式类似，如果 Polaris 从第 $i1$ 座大楼的第 $j1$个商户，以及第 $i2$ 座大楼的第 $j2$ 个商户那里进原料，做出的披萨质量和价格就是 $\sum\limits_{k=1}^{n} {q_{i1,j1,k} \times q_{i2,j2,k}}$。她会严格按照这个价格将披萨卖给 Tarat 和 Ratar，不收取额外费用。

计算之后，他们发现剩余的时间不是很多。Tarat 和 Ratar 决定把原料商限制在两座楼 $b1$ 和 $b2$ 里 $(1 \leq b1<b2 \leq b)$。接下来的每一天，他们都会从两座楼里的所有 $2\times n$个商店里进原料，请 Polaris 做出 $n$ 个披萨。具体来说，Polaris 将指定一个排列 $p=(p_1,p_2,..,p_n)$，之后她做出的 $n$ 个披萨中，第 $i$ 个披萨的原料来自第 $b1$ 个大楼的第 $i$ 个供货商，以及第 $b2$ 个大楼的第 $p_i$ 个供货商，因此第 $i$ 个披萨的价格是 $\sum\limits_{i=1}^{n} \sum\limits_{k=1}^{n} q_{b1,i,k} \times q_{b2,p_i,k}$。

很明显，排列 $p$ 一共有 $n!$ 种可能，因此 Tarat 和 Ratar 决定在这里逗留 $n!$ 天，在这些日子里，Polaris 将严格按照字典序，枚举 p 的每一种可能来制作披萨。我们假设某一天制作的披萨价格为$Prize=(Prize_1,Prize_2,Prize_3,\text{...},Prize_n)$。

还有最后一个问题。Tarat 和 Ratar 都是懒人，而 Polaris 的店面在很隐秘的地方，要走很久的路才能到。每当 Polaris 做好一个披萨，她就会要求他们随便派一个人马上过来取，并支付所需费用。Tarat 和 Ratar 讨论了很久，最终得到了一个看似很公平的方案：

在开始的安排中，Tarat 和 Ratar 将均摊吃披萨的费用。由于 $1$ 元钱不能分割，当某个 $Prize_x$ 是奇数时，就有一个人要多出 $1$ 元钱。在最终安排中，Tarat 和 Ratar 会让 Polaris 提前告诉他们今天所有披萨的价格 $Prize$。如果所有的 $Prize$ 都是偶数，他们会多花几个钱，让城里的另一个附近的朋友 Albus 帮他们拿披萨。否则他们将轮流出动，而待在住处的人的代价就是要负责今天所有披萨价格的零头。在第一个这样的日子里，Tarat 将负责去拿披萨，而第二次遇到则是 Ratar 负责，第三次遇到又由 Tarat 负责，如此往复。

Tarat 并不在乎钱，其实他也不是很在乎披萨，他只是很懒不想动。

特别是不想比 Ratar 还忙。

但是 Tarat 发现根据上面的计划，只会有两种可能：

1. 他比 Ratar 多跑一天路。
2. 他和 Ratar 负责跑路拿披萨的天数相同。

而 Ratar 是一个很死板的人，她会强制两个人严格按照规则办事。

于是 Tarat 偷懒的最后希望就在于两座建筑 $b1$ 和 $b2$ 的选择，虽然这个选择权在 Ratar 手上。

他相信只要他说服 Ratar 选择某两座建筑 $b1$ 和 $b2$，他就不需要比 Ratar 多跑一天路。

但是 Ratar 看出了他的计划。因此她想要选择两座建筑 $b1$ 和 $b2$ $(b1<b2)$，使得根据上面的安排，Tarat 需要多跑一天的路。

你的任务，就是求出有多少种可行的建筑对 $(b1,b2)$，使得 Tarat 必须多跑一天路。

输入格式

本题有多组数据，第一行就是数据组数 $T$。

每组数据的开始是两个数：$n$ 和 $b$，分别表示披萨原料的种数和 Pizzahut 大楼的数量。注意一座 Pizzahut 大楼里的原料商数量也恰好为 $n$。

现在输入矩阵 $q$ 的信息，$q_{i,j,k}$ 表示第 $i$ 个建筑中第 $j$ 个原料商提供的第 $k$ 种原料质量。接下来将依次输入 $b$ 个矩阵，依次表示第 $i$ 个建筑的信息。

为了防止输入文件过于庞大，我们把输入方式分为两种：raw 和 random，在每个建筑信息的第一行进行标识。

如果输入方式是 raw，那么接下来 $n$ 行 $n$ 列表示 $q_i$ 的值。

如果输入方式是 random，那么下一行将有三个参数 $si,pi,ai$ 用于生成矩阵 $q_i$。

为了生成矩阵 $q_i$，需要先生成长度为 $n^2$ 的序列 $xi_j$。

$xi_j$ 的生成方式如下：

$xi_1 = si,xi_k = (pi \times xi_{k-1} + ai)\text{mod}\ M$。

$M = 2^{32} = 4294967296$。

之后我们可以通过 $xi_j$ 计算 $q_{i,j,k}$：

$q_{i,j,k} = (\frac{\text{floor}(xi_{(j-1) \times n + k})}{D}\text{mod}\ 100)+1$

$D = 2^{12} = 4096$。

$\text{floor}(x)$ 表示取下整。样例里有这种输入方式的一个例子。

注意：一个数据里可以同时存在两种输入方式。$si,pi,ai$ 是纯粹的随机数种子，分析它们对解题完全没有意义。

输出格式

$T$ 行，每行一个数表示答案。

3
3 3
raw
82 51 44
41 10 38
23 33 58
raw
19 84 64
17 43 44
30 81 57
raw
61 84 31
52 90 82
29 16 45
4 8
random
11708 9521 15107
random
5874 19373 36492
random
11504 36617 16182
random
33487 35453 8669
random
33741 25749 9927
random
12099 17221 19740
random
5587 2589 14716
random
36950 17607 32881
10 2
random
29163 283 8737
raw
55 23 6 47 7 89 4 96 77 97
19 20 85 35 72 70 77 71 32 82
44 40 75 68 9 66 10 40 51 46
47 64 73 77 40 49 89 81 50 95
20 88 5 98 52 3 3 26 35 48
25 55 29 49 30 27 70 73 85 93
6 27 81 74 51 21 76 71 12 66
6 49 65 59 92 70 95 56 4 21
98 39 50 13 22 38 31 70 63 29
3 60 93 22 81 95 7 21 12 49

1
5
1

样例说明

在第一个数据中，只有 $(b1,b2)=(1,2)$ 满足要求。为了对题目有更深了解，我们可以来分析这个情况。用 $(i,j)$ 表示 Polaris 使用第 $1$ 个建筑里的第 $i$ 个供货商和第 $2$ 个建筑里第 $j$ 个供货商两个商人的原料做出 Pizza 的价格。

那么：

• $(1, 1)$ 的价格是 $82 \times 19+51 \times 84+44 \times 64 = 8658$；
• $(1, 2)$ 的价格是 $82 \times 17+51 \times 43+44 \times 44 = 5523$；
• $(1, 3)$ 的价格是 $82 \times 30+51 \times 81+44 \times 57 = 9099$；
• $(2, 1)$ 的价格是 $41 \times 19+10 \times 84+38 \times 64 = 4051$；
• $(2, 2)$ 的价格是 $41 \times 17+10 \times 43+38 \times 44 = 2799$；
• $(2, 3)$ 的价格是 $41 \times 30+10 \times 81+38 \times 57 = 4206$；
• $(3, 1)$ 的价格是 $23 \times 19+33 \times 84+58 \times 64 = 6921$；
• $(3, 2)$ 的价格是 $23 \times 17+33 \times 43+58 \times 44 = 4362$；
• $(3, 3)$ 的价格是 $23 \times 30+33 \times 81+58 \times 57 = 6669$。

在所有的 $3!=6$ 天中，有 $5$ 天出现了至少 $1$ 个奇数价格的披萨，需要两个人跑腿：

• $[(1, 1), (2, 2), (3, 3)]$；
• $[(1, 2), (2, 1), (3, 3)]$；
• $[(1, 2), (2, 3), (3, 1)]$；
• $[(1, 3), (2, 1), (3, 2)]$；
• $[(1, 3), (2, 2), (3, 1)]$。

因此有三天 Tarat 要出门拿披萨，有两天 Ratar 要出门。

而 $(1,1), (2,3), (3,2)$ 这一天因为披萨价格都是偶数，他们会让 Albus 去拿披萨。

在第二个数据中，使用了 random 的构造方法。为了让你验证你的构造正确性，我们给出 $x1_i$ 的值和 $q_1$ 的值：

$x1_1 = 11708,x1_2 = 111486975,x1_3 = 610581970,x1_4 = 2260199989$；

$x1_5 = 1577957416,x1_6 = 4231938731,x1_7 = 1200469182,x1_8 = 759122273$；

$x1_9 = 3468184468,x1_{10} = 875763287,x1_{11} = 1610749098,x1_{12} = 2908930445$；

$x1_{13} = 1977657344,x1_{14} = 138961667,x1_{15} = 204119446, x1_{16} = 2096042681$。

$q_{1, 1, 1} = 3, q_{1, 1, 2} = 19, q_{1, 1, 3} = 68, q_{1, 1, 4} = 7$；

$q_{1, 2, 1} = 44, q_{1, 2, 2} = 89, q_{1, 2, 3} = 84, q_{1, 2, 4} = 33$；

$q_{1, 3, 1} = 25, q_{1, 3, 2} = 10, q_{1, 3, 3} = 50, q_{1, 3, 4} = 89$；

$q_{1, 4, 1} = 27, q_{1, 4, 2} = 27, q_{1, 4, 3} = 34, q_{1, 4, 4} = 30$。

你可以手动 watch 判断正确性。这个数据里合法的 $(b1,b2)$ 是 $(1, 4), (1, 6), (2, 5), (4, 5), (4, 6)$。

数据规模与约定

对于所有数据：$1 \leq q_{i,j,k} \leq 100$，生成数据用的 $si,pi,ai \leq 4 \times 10^4$，$T \leq 5$，$\sum{b} \leq 8000$。

考虑读入数据可能占用大部分时间，测试数据输入文件大小 $\leq 3000\text{KB}$。

在大数据中，以 raw 读入的 $q_i$ 大约有 $3\%$~$10\%$，也就是说大部分数据是 random 的。

• 对于 $100\%$ 的数据：$n \leq 60$，$b \leq 4000$，$\sum{b} \leq 8001$。

题目来源

数学