El tres en raya pero con gatos.

Entrada

La primera línia indica els casos de prova a considerar. Cada cas tindrà dues línies, la primera tindrà el nombre de files (F) i la segona el nombre de columnes (C), seguit de una matriu F*C amb una serie de nombres que seràn 1 (gat) o 0 (res). (Els gats utilitzats en una ratlla no poden utilitzar-se per formar una altre).

Sortida

Per a cada cas hauràs de donar la quantitat de línies que es poden formar amb els gats de la matriu, en format de un nombre únic.

Exemple d'Entrada

2
3 3
1 0 1
1 0 1
1 1 1
5 5
1 1 1 0 1
0 1 1 1 1
1 0 1 0 1
1 0 0 1 1
1 1 1 0 1

Exemple de Sortida

2
5