You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 2.0 s

Memory Limit: 512.0 MB

Description

Thakur is playing a simple character matching game. Obviously his target is to earn as many points as possible.

The game is played in \(N\) rounds. Before the game starts thakur has to guess a string \(S\) of length \(M\) and he can change this string at most once in the entire game . In each of the \(i^{th}\) round a string \(T_i\) consisting only lowercase letters of size \(M\) appears.

The score of the \(i^th\) round is the number of indices \(j\) where \(S_j\)==\(Ti_j\)

What is the maximum score thakur can earn from the game ?

Input

first line takes an integer \(Tc\) : number of testcases
first line of each testcase takes two integer \(N,M\) : number of rounds, size of string in each round
each of the next \(N\) line takes a string \(T\) of length \(M\)
\(1 <= Tc <= 100\)
\(1 <= N,M <= 2*10^5\)

sum of \(N*M\) over all testcase will not exceed \(2*10^5\)

Output

For each testcase, print a single integer: maximum point thakur can earn from the game.

Sample

3
2 3
abc
abc
4 3
aba
abd
aba
abd
5 4
aaaa
baba
cdcb
bcad
abab

6
11
12

in first testcase :
thakur can start with S = "abc" and do no need to change the string to gain max point 6

in second testcase:
thakur can start with S = "aba" and in the 4th round change the strin to S' = "abd" to gain max 11 point

in third testcase:
thakur can start with S = "aaaa" and in the third round change the string to S' = "cbab" to gain max 12 point