flood

Vous vous intéressez à la propagation d'un virus sur des populations de bactéries. On considère un environnement constitué d'une grille carrée où chaque case est occupée par une bactérie d'un certain type représenté par un entier. Il existe deux souches du virus que vous étudiez : alpha et béta. Les deux souches sont capables de se propager d'un individu infecté à un individu voisin du même type. La souche alpha est également capable de se propager à un individu voisin d'un autre type qui est alors infecté par la souche béta, moins infectieuse. Chaque bactérie a 4 voisins (haut, bas, droite, gauche) (sauf si elle est au bord de la grille).

Étant donné une grille carrée et les coordonnées d'une bactérie infectée par la souche alpha, vous devez calculer combien de bactéries vont être infectées au total.

Entrée : La première ligne contient le nombre de test cases. Chaque test case est précédé d'une ligne vide. Chaque test case commence par une ligne contenant n, la taille de la grille (le coté du carré), et c, le nombre de types de bactéries. La seconde ligne de chaque test case contient les coordonnées de la première bactérie infectée (n° ligne, n° colonne, en numérotant à partir de 0 dans le coin en haut à gauche). Suivent ensuite les n lignes de n entiers qui constituent la grille. Ordres de grandeur : 0 < n < 100 et 0 < c < 15

Sortie : Pour chaque test case, vous devez renvoyer une ligne contenant le nombre de bactéries infectées. Contrairement à l'entrée, ne mettez pas de ligne vide entre chaque réponse.

Input

4

10 2
4 6
0 1 0 0 0 1 1 1 1 0
0 1 0 0 1 1 1 0 0 0
0 0 0 0 1 1 0 0 0 1
0 0 1 1 1 0 1 1 1 0
1 1 0 0 0 0 0 1 0 0
0 1 0 0 0 1 1 1 1 0
0 1 1 1 1 1 1 0 0 0
0 0 0 0 1 1 0 0 0 1
0 0 1 1 1 0 1 1 1 0
1 1 0 0 0 0 0 1 0 0

10 3
4 6
0 1 0 2 0 1 1 1 1 0
0 1 0 2 1 1 1 2 2 0
0 0 0 2 1 1 0 0 0 1
0 0 1 1 1 0 1 1 1 0
1 1 0 0 0 0 0 1 0 0
0 1 0 0 0 2 2 2 1 0
0 1 1 1 2 2 1 0 0 0
0 0 0 0 1 1 0 0 0 1
0 2 2 2 2 0 1 1 1 0
1 1 0 0 2 2 2 1 0 0

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

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

Télécharger l'entrée

Output

43
36
12
9

Télécharger la sortie