Hay una arena cíclica de $n$ dimensiones para un robot: cada coordenada es un residuo módulo $p = 998\,244\,353$. Cada cartucho contiene una orden: un vector de desplazamiento de $n$ residuos módulo $p$. Aplicar un cartucho una vez mueve al robot exactamente según el vector escrito en él (cada coordenada se toma módulo $p$).

Un mando a distancia puede contener exactamente $n$ cartuchos. Llamamos universal a un mando a distancia si, utilizando únicamente los cartuchos instalados en él y aplicando cada uno de ellos un número arbitrario de veces, el robot puede ir de cualquier celda de la arena a cualquier otra.

Hay $m$ cartuchos en el almacén. El cartucho $i$ contiene el vector de desplazamiento $v_i$.

Hay $q$ informes independientes de inspección del almacén. En el informe $j$, únicamente los cartuchos con índices de $l_j$ a $r_j$ siguen vigentes: se pueden tomar del almacén gratuitamente, mientras que todos los demás cartuchos del almacén han caducado y su uso está prohibido.

Además, para cada informe se permite fabricar cualquier cantidad de cartuchos nuevos vigentes. Cada uno de estos cartuchos cuesta una moneda, y su vector de desplazamiento se puede elegir arbitrariamente (incluso con vectores coincidentes). Los cartuchos fabricados no se conservan entre informes.

Para cada informe, determina el número mínimo de monedas necesario para ensamblar dos mandos a distancia universales con cartuchos vigentes. Cada cartucho se puede usar como máximo una vez y únicamente en un mando a distancia.

Entrada

La primera línea contiene un entero $1 \le t \le 1000$: el número de casos de prueba.

Para cada caso de prueba, la primera línea contiene tres enteros $n$, $m$ y $q$: la dimensión de la arena, el número de cartuchos en el almacén y el número de informes de inspección, respectivamente ($1 \le n \le 150$, $1 \le m,q \le 3 \cdot 10^5$). Además, se garantiza que la suma de $n \cdot m$ y la suma de $q$ sobre todos los casos de prueba no superan $3 \cdot 10^5$ cada una.

A continuación siguen $m$ líneas, cada una con $n$ enteros $v_{i,1}, v_{i,2}, \ldots, v_{i,n}$: el vector de desplazamiento del cartucho $i$ ($0 \le v_{i,k} < p$).

A continuación siguen $q$ líneas, cada una con dos enteros $l_j$ y $r_j$ ($1 \le l_j \le r_j \le m$): en el informe de inspección correspondiente, únicamente los cartuchos con índices de $l_j$ a $r_j$ siguen vigentes.

Salida

Para cada informe de inspección, imprime un entero: el número mínimo de monedas necesario para ensamblar dos mandos a distancia universales con cartuchos vigentes.

Ejemplos

Entrada 1

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

Salida 1

2
1
1
0

Entrada 2

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

Salida 2

2
1
1