D. Similarity
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After Da7doo7 got fired he wanted to get an interview for another job so he hacked the PC of an HR to make his CV similar to the CVs of the employees. He needed your help and he gave you the information more formally.

Given $$$n$$$ strings of length $$$m$$$, you have to construct a string of length $$$m$$$ with maximum total similarity.

We define the similarity of two strings $$$a,b$$$ to be the number of indices $$$i$$$ $$$(1\le i\le m)$$$ where $$$a_i=b_i$$$.

The total similarity is equal to the sum of similarities of the string you constructed with all $$$n$$$ strings you are given.

We are not interested in the string itself, we only want the total similarity to be maximum possible.

Please print the maximum possible total similarity.

Input

The first line contains an integer $$$T$$$ $$$(1\le T\le 50)$$$ representing the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ $$$(1\le n,m\le 50)$$$ — the number of strings and their length.

The $$$i$$$-th of the following $$$n$$$ lines of each test case contain a string $$$s_i$$$ of length $$$m$$$.

Output

For each test case, print the maximum possible total similarity in a single line.

Example
Input
2
3 3
abc
ebd
fbd
2 3
abc
aff
Output
6
4
Note

In the first test case for example:

One of the possible strings with the maximum similarity is $$$ebd$$$,

The similarity of $$$s_1$$$ and $$$ebd$$$ is equal to $$$1$$$.

The similarity of $$$s_2$$$ and $$$ebd$$$ is equal to $$$3$$$.

The similarity of $$$s_3$$$ and $$$ebd$$$ is equal to $$$2$$$.

To the total similarity is: $$$1+3+2=6$$$