Programacion Competitiva Bolivia

El ajedrez se juega en un tablero de 8x8 con diferentes tipos de fichas, que se mueven de diferente forma.
Se esta evaluando adicionar un nuevo tipo de ficha al tablero y uno de los aspectos que queremos
analizar, es su alcance en el tablero.

El movimiento de una ficha, se puede determinar por movimientos horizontales y verticales. Por
ejemplo, el caballo se puede mover una casilla horizontalmente y dos verticales o dos horizontales
y una vertical.

En el diagrama se puede observar como un caballo (la casilla C), en un movimiento, puede
moverse a 8 posiciones (las marcadas con *).


·*·*·
*···*
··C··
*···*
·*·*·


Dados los tipos de movimientos de la nueva ficha, determinar a cuantas casillas puede llegar
despues de varios movimientos en un tablero de NxN si la ficha comenzara en una de las esquinas del tablero.

Entrada

Q = Numero de casos de prueba
Por cada caso de prueba:
N = Tamaño del tablero cuadrado
NT = Numero de tipos de movimiento
Por cada tipo de movimiento
x y , donde x es el movimiento horizontal (izquierda o derecha), e y es movimiento vertical(arriba o abajo)

Salida

Por cada caso de prueba, el numero de casillas que la nueva pieza de ajedrez puede alcanzar en
varias movidas.

Ejemplos de Entrada

1
3
8
1 2
1 -2
2 1
2 -1
-2 1
-2 -1
-1 2
-1 -2

Ejemplos de Salida

8

El caso de ejemplo es el del caballo, tenemos ocho tipos de movimientos indicados en la entrada

X  | Y
-------
 1 |  2
 1 | -2
 2 |  1
 2 | -1
-1 |  2
-1 | -2
-2 |  1
-2 | -1

Partiendo de una esquina puede llegar a 8 lugares en múltiples movimientos.