Narek is too lazy to create the third problem of this contest. His friend Artur suggests that he should use ChatGPT. ChatGPT creates 𝑛 problems, each consisting of 𝑚 letters, so Narek has 𝑛 strings. To make the problem harder, he combines the problems by selecting some of the 𝑛 strings possibly none and concatenating them without altering their order. His chance of solving the problem is defined as 𝑠𝑐𝑜𝑟𝑒𝑛−𝑠𝑐𝑜𝑟𝑒𝑐, where 𝑠𝑐𝑜𝑟𝑒𝑛 is Narek's score and 𝑠𝑐𝑜𝑟𝑒𝑐 is ChatGPT's score.

Narek calculates 𝑠𝑐𝑜𝑟𝑒𝑛 by examining the selected string (he moves from left to right). He initially searches for the letter "𝚗", followed by "𝚊", "𝚛", "𝚎", and "𝚔". Upon finding all occurrences of these letters, he increments 𝑠𝑐𝑜𝑟𝑒𝑛 by 5 and resumes searching for "𝚗" again (he doesn't go back, and he just continues from where he left off).

After Narek finishes, ChatGPT scans through the array and increments 𝑠𝑐𝑜𝑟𝑒𝑐 by 1 for each letter "𝚗", "𝚊", "𝚛", "𝚎", or "𝚔" that Narek fails to utilize (note that if Narek fails to complete the last occurrence by finding all of the 5 letters, then all of the letters he used are counted in ChatGPT's score 𝑠𝑐𝑜𝑟𝑒𝑐, and Narek doesn't get any points if he doesn't finish finding all the 5 letters).

Narek aims to maximize the value of 𝑠𝑐𝑜𝑟𝑒𝑛−𝑠𝑐𝑜𝑟𝑒𝑐 by selecting the most optimal subset of the initial strings.

Input
In the first line of the input, you're given a single integer 𝑡 (1≤𝑡≤105), the number of test cases. Then the description of each test case follows.

In the first line of each test case, you're given two integers 𝑛,𝑚 (1≤𝑛,𝑚≤103), the number of strings and the length of each string.

In the next 𝑛 lines, you're given 𝑛 strings, each having a length of 𝑚. The strings only contain lowercase letters of the English alphabet.

The sum of values of 𝑛⋅𝑚 over all test cases does not exceed 106.

Output
For each test case, output a single integer: the maximal possible value of 𝑠𝑐𝑜𝑟𝑒𝑛−𝑠𝑐𝑜𝑟𝑒𝑐.

Example
inputCopy
4
5 2
nn
aa
rr
ee
kk
1 5
narek
1 4
nare
5 7
nrrarek
nrnekan
uuuuuuu
ppppppp
nkarekz
outputCopy
0
5
0
7
Note
In the first test case, one of the optimal answers is when Narek doesn't choose any of the strings, so the answer is 0. He can alternatively choose all the strings. In this case, the full string becomes "nnaarreekk". Narek can choose the first appearances of all letters and add 5 to the score. His opponent will add 1 for all second appearances, which will be 5 in total. So the answer will be 5−5=0.

In the third test case, the only optimal answer is when Narek doesn't choose the string. Note that if he were to choose the string, he wouldn't be able to find the last letter "k", so his score would stay at 0 instead of becoming 5. Then ChatGPT would add 4 for all of the 4 letters, and the answer would become 0−4=−4.

In the last test case, Narek needs to choose the first and the last strings. After putting these two next to each other, he gets "𝑛𝑟𝑟𝑎𝑟𝑒𝑘𝑛𝑘𝑎𝑟𝑒𝑘𝑧". Narek can choose the letters marked with red and add 10 to his score. Since the black colored letters Narek left behind are eligible for the opponent to claim (they are used in the word "narek"), the opponent adds all other letters to the score and gets a score of 3. Therefore, the answer is 10−3=7.