Minimum Number of Enclosures

You are given several test cases. In each test case, there are S species with specific space requirements and a compatibility matrix. Two species can be placed in the same enclosure if and only if they are mutually compatible. Formally, for any two species i and j in the same enclosure, the element of the compatibility matrix at row i, column j must be 1.

Your task is to determine the minimum number of enclosures needed to house all species. Although space requirements are provided, they do not influence the compatibility grouping.

The compatibility condition can be formally expressed in LaTeX as:

[ \text{For any two species } i \text{ and } j \text{ in the same enclosure, } C_{ij} = 1 ]

Solve the problem so that each test case returns the minimum number of enclosures required.

inputFormat

The input is read from stdin and has the following format:

T
S
space_reqs[0] space_reqs[1] ... space_reqs[S-1]
compatibility_matrix_row_1 (S integers separated by space)
...
compatibility_matrix_row_S
... (next test cases)

Where:

• T is the number of test cases.
• S is the number of species in the test case.
• space_reqs is a list of S integers (space requirements).
• compatibility_matrix is an SxS matrix where each row contains S integers (either 0 or 1) representing the compatibility between species.

outputFormat

For each test case, print the minimum number of enclosures required, each on a new line. The output is written to stdout.

## sample

1
3
100 200 300
1 1 0
1 1 1
0 1 1

2