ロボットのための $n$ 次元の巡回アリーナがあります。各座標は $p = 998\,244\,353$ を法とする剰余です。各カートリッジには命令、すなわち $p$ を法とする $n$ 個の剰余からなる移動ベクトルが入っています。カートリッジを1回適用すると、ロボットはそこに書かれたベクトルの分だけ正確に移動します（各座標は $p$ を法として計算されます）。

リモコンにはちょうど $n$ 個のカートリッジを装着できます。装着されているカートリッジだけを使い、それぞれを任意の回数適用することで、ロボットがアリーナの任意のマスから他の任意のマスへ移動できるとき、そのリモコンを万能と呼びます。

倉庫には $m$ 個のカートリッジがあります。$i$ 番目のカートリッジには移動ベクトル $v_i$ が入っています。

独立した倉庫検査報告が $q$ 件あります。$j$ 番目の報告では、添字が $l_j$ から $r_j$ までのカートリッジだけが使用期限内です。これらは倉庫から無料で持ち出せますが、倉庫内のその他のカートリッジはすべて期限切れで、使用は禁止されています。

さらに、各報告について、使用期限内の新しいカートリッジを任意の個数製造できます。そのようなカートリッジは1個につきコイン1枚がかかり、移動ベクトルは任意に選べます（同じベクトルを選んでもかまいません）。製造したカートリッジは報告の間で引き継がれません。

各報告について、使用期限内のカートリッジから2台の万能リモコンを組み立てるために必要なコインの最小枚数を求めてください。各カートリッジは高々1回しか使えず、1台のリモコンにしか装着できません。

入力

最初の行には、テストケース数を表す整数 $t$（$1 \le t \le 1000$）が1つ与えられます。

各テストケースの最初の行には、アリーナの次元、倉庫内のカートリッジ数、検査報告数をそれぞれ表す3つの整数 $n, m, q$ が与えられます（$1 \le n \le 150$、$1 \le m, q \le 3 \cdot 10^5$）。さらに、すべてのテストケースにわたる $n \cdot m$ の総和と $q$ の総和は、いずれも $3 \cdot 10^5$ を超えないことが保証されます。

続く $m$ 行にはそれぞれ、$i$ 番目のカートリッジの移動ベクトルを表す $n$ 個の整数 $v_{i,1}, v_{i,2}, \ldots, v_{i,n}$ が与えられます（$0 \le v_{i,k} < p$）。

続く $q$ 行にはそれぞれ、2つの整数 $l_j, r_j$（$1 \le l_j \le r_j \le m$）が与えられます。対応する検査報告では、添字が $l_j$ から $r_j$ までのカートリッジだけが使用期限内です。

出力

各検査報告について、使用期限内のカートリッジから2台の万能リモコンを組み立てるために必要なコインの最小枚数を表す整数を1つ出力してください。

入出力例

入力 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