Hackers are once again trying to create entertaining phrases using the output of neural networks. This time, they want to obtain an array of strings $$$a$$$ of length $$$n$$$.

Initially, they have an array $$$c$$$ of length $$$n$$$, filled with blanks, which are denoted by the symbol $$$*$$$. Thus, if $$$n=4$$$, then initially $$$c=[*,*,*,*]$$$.

The hackers have access to $$$m$$$ neural networks, each of which has its own version of the answer to their request – an array of strings $$$b_i$$$ of length $$$n$$$.

The hackers are trying to obtain the array $$$a$$$ from the array $$$c$$$ using the following operations:

Choose a neural network $$$i$$$, which will perform the next operation on the array $$$c$$$: it will select a random blank, for example, at position $$$j$$$, and replace $$$c_j$$$ with $$$b_{i, j}$$$.
For example, if the first neural network is chosen and $$$c = [*, \text{«like»}, *]$$$, and $$$b_1 = [\text{«I»}, \text{«love»}, \text{«apples»}]$$$, then after the operation with the first neural network, $$$c$$$ may become either $$$[\text{«I»}, \text{«like»}, *]$$$ or $$$[*, \text{«like»}, \text{«apples»}]$$$.
Choose position $$$j$$$ and replace $$$c_j$$$ with a blank.

Unfortunately, because of the way hackers access neural networks, they will only be able to see the modified array $$$c$$$ after all operations are completed, so they will have to specify the entire sequence of operations in advance.

However, the random behavior of the neural networks may lead to the situation where the desired array is never obtained, or obtaining it requires an excessive number of operations.

Therefore, the hackers are counting on your help in choosing a sequence of operations that will guarantee the acquisition of array $$$a$$$ in the minimum number of operations.

More formally, if there exists a sequence of operations that can guarantee obtaining array $$$a$$$ from array $$$c$$$, then among all such sequences, find the one with the minimum number of operations, and output the number of operations in it.

If there is no sequence of operations that transforms array $$$c$$$ into array $$$a$$$, then output $$$-1$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 500$$$) — the length of the original array $$$a$$$ and the number of neural networks, respectively.

The second line of each test case contains the array $$$a$$$, consisting of $$$n$$$ strings $$$a_i$$$ ($$$1 \le |a_i| \le 10$$$), separated by spaces.

The next $$$m$$$ lines of each test case contain the arrays $$$b_i$$$ — one in each line, consisting of $$$n$$$ strings $$$b_{i, j}$$$ ($$$1 \le |b_{i,j}| \le 10$$$), separated by spaces.

It is guaranteed that the sum of $$$|a_i|$$$ and $$$|b_{i, j}|$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$, and that the sum of $$$n \cdot m$$$ across all test cases also does not exceed $$$2 \cdot 10^5$$$.

It is guaranteed that the input strings consist only of characters from the Latin alphabet in both lowercase and uppercase.

Note that the length of each individual input string does not exceed $$$10$$$.

Output

Output $$$t$$$ numbers — one number for each test case, each on a separate line.

If there exists a sequence of operations that guarantees obtaining array $$$a$$$ from the $$$i$$$-th test case, then the $$$i$$$-th number is the number of operations in the minimum such sequence.

Otherwise, for the $$$i$$$-th number, output $$$-1$$$.

Idx	Name	Rating
A	Ideal Generator	800
B	Expensive Number	900
C	Simple Repetition	1000
D	Skibidi Table	1400
E	Min Max MEX	1500
F	Hackers and Neural Networks	1800
G	Shorten the Array	1900

Codeforces Round 1016 (Div. 3)