로봇을 위한 $n$차원 순환 공간이 있다. 각 좌표는 $p = 998\,244\,353$을 법으로 하는 나머지이다. 각 카트리지에는 명령 하나가 들어 있다. 이 명령은 $p$를 법으로 하는 나머지 $n$개로 이루어진 이동 벡터이다. 카트리지를 한 번 적용하면 로봇은 그 안에 적힌 벡터만큼 정확히 이동한다(각 좌표는 $p$로 나눈 나머지를 취한다).

리모컨 하나에는 정확히 $n$개의 카트리지를 장착할 수 있다. 장착된 카트리지만 사용하고 각각을 임의의 횟수만큼 적용하여 로봇이 공간의 어떤 칸에서든 다른 어떤 칸으로든 이동할 수 있다면, 그 리모컨을 범용이라고 부른다.

창고에는 $m$개의 카트리지가 있다. $i$번째 카트리지에는 이동 벡터 $v_i$가 들어 있다.

서로 독립적인 창고 점검 보고서가 $q$개 있다. $j$번째 보고서에서는 번호가 $l_j$부터 $r_j$까지인 카트리지만 유효한 상태로 남아 있어 창고에서 무료로 가져갈 수 있다. 창고의 다른 모든 카트리지는 유효 기간이 지나 사용이 금지된다.

또한 각 보고서에서는 유효한 새 카트리지를 원하는 만큼 제조할 수 있다. 이러한 카트리지 하나를 제조하는 데는 동전 하나가 들며, 이동 벡터를 임의로 선택할 수 있다(동일한 벡터도 허용된다). 제조한 카트리지는 다른 보고서로 넘어갈 때 유지되지 않는다.

각 보고서에 대해, 유효한 카트리지로 범용 리모컨 두 개를 조립하는 데 필요한 최소 동전 수를 구하여라. 각 카트리지는 최대 한 번만 사용할 수 있으며, 하나의 리모컨에만 사용할 수 있다.

입력

첫 번째 줄에는 테스트 케이스 수를 나타내는 정수 $t$ 하나가 주어진다($1 \le t \le 1000$).

각 테스트 케이스의 첫 번째 줄에는 정수 $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$번째 카트리지의 이동 벡터를 나타내는 정수 $v_{i,1}, v_{i,2}, \ldots, v_{i,n}$이 $n$개 주어진다($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