Alice was walking down the street. When she saw Bob on the other side, she shouted: “HELLO, BOB!”
“Hi, Alice!” responded Bob from afar and they both hurried to meet in the middle of the street.
“Bob! Why didn't you shout back when I said hello?” asked Alice, apparently a bit annoyed.
Bob, surprised, defended himself: “What? But I did. I said 'Hi, Alice!'”.
Alice smiled. “Oh, I see. You were too quiet. To shout, you must speak in uppercase!”
“Ah, OK. No, wait. I said 'Hi', which has an uppercase letter, see?”
“That makes no difference. The whole word must be in uppercase, LIKE THIS. Words that are entirely in uppercase are twice as loud as normal words.”
“Your shouting is only twice as loud as normal?” laughed Bob. “That's not very much.”
“Just you wait!” responded Alice and produced a terrible high-pitched squeal: “*Eeeeeeeee!*”
“How did you do that?”
“You just have to add asterisks. All words between them are three times louder.”
“Cool. Let's see who can shout louder!” proposed Bob and screamed: “*AAA aaa* a a aargh!”
Alice countered: “*aaaaa*!”
“I won!” exclaimed Bob. “I used three normal words, one word that was thrice as loud, and one that was six times as loud. You could say I scored 1+1+1+3+6=12 loudness points.”
“No, you've got it all wrong. You have to count the average, not the sum. So you only scored 2.4 points. And I scored 3, so I won!” concluded Alice.
You are given several sentences. Your task is to find the loudest one.
The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.
The first line of each test case contains an integer n (1 ≤ n ≤ 100), the number of sentences. Each of the following n lines contains one sentence. Each line is at most 500 characters long.
A word is a maximal non-empty sequence of consecutive upper- and lowercase letters of the English alphabet. Words in a sentence are separated by spaces ( ), punctuation (,.:;'"!?-) and asterisks (*). No other characters appear in the input. Each sentence contains at least one word. There is an even number of asterisks in each sentence. The input file for the easy subproblem S1 contains no asterisks.
For each test case, output one line with a single integer – the index of the loudest sentence (i.e., the one whose average word loudness is the highest), counting from 1. If there are multiple sentences tied for being the loudest, output the smallest of their indices.
Input:
2
2
HELLO, BOB!
Hi, Alice!
4
*AAA aaa* a a aargh!
*aaaaa*
*note*that asterisks do not*nest***
* * THIS IS NOT BETWEEN ASTERISKS * *Output:
1
2