有一个供机器人活动的 $n$ 维循环场地：每个坐标都是模 $p=998\,244\,353$ 的剩余类。每个指令盒中包含一条指令，即由 $n$ 个模 $p$ 的剩余类组成的位移向量。使用一个指令盒一次，会使机器人恰好按照其中记录的向量移动（每个坐标均对 $p$ 取模）。

一个遥控器恰好可以装入 $n$ 个指令盒。如果仅使用装入其中的指令盒，并且每个指令盒可以使用任意次，就能使机器人从场地中的任意格子到达任意其他格子，那么我们称这个遥控器为通用遥控器。

仓库中有 $m$ 个指令盒。第 $i$ 个指令盒中记录的位移向量为 $v_i$。

有 $q$ 份相互独立的仓库检查报告。在第 $j$ 份报告中，只有编号从 $l_j$ 到 $r_j$ 的指令盒仍未过期，可以从仓库中免费取用；仓库中所有其他指令盒均已过期，禁止使用。

此外，在每份报告中，都允许制造任意数量的新指令盒，每个这样的指令盒都未过期。制造每个指令盒需要花费一枚硬币，其位移向量可以任意选择（允许向量相同）。制造的指令盒不会在不同报告之间保留。

对于每份报告，求用未过期的指令盒组装两个通用遥控器所需的最少硬币数。每个指令盒最多只能使用一次，并且只能装入一个遥控器。

输入格式

第一行包含一个整数 $t$（$1\le t\le1000$），表示测试用例的数量。

对于每个测试用例，第一行包含三个整数 $n$、$m$ 和 $q$，分别表示场地的维数、仓库中的指令盒数量和检查报告的数量（$1\le n\le150$，$1\le m,q\le3\cdot10^5$）。此外，保证所有测试用例的 $n\cdot m$ 之和与 $q$ 之和分别不超过 $3\cdot10^5$。

接下来 $m$ 行，每行包含 $n$ 个整数 $v_{i,1},v_{i,2},\ldots,v_{i,n}$，表示第 $i$ 个指令盒的位移向量（$0\le v_{i,k}<p$）。

接下来 $q$ 行，每行包含两个整数 $l_j$ 和 $r_j$（$1\le l_j\le r_j\le m$），表示在对应的检查报告中，只有编号从 $l_j$ 到 $r_j$ 的指令盒仍未过期。

输出格式

对于每份检查报告，输出一个整数，表示用未过期的指令盒组装两个通用遥控器所需的最少硬币数。

样例

输入格式 1

1
1 3 4
0
1
2
1 1
2 2
3 3
1 3

输出格式 1

2
1
1
0

输入格式 2

1
2 4 3
1 0
0 1
0 1
0 1
1 2
1 3
1 4

输出格式 2

2
1
1