E - Corrupted Gradebook

A gradebook has been corrupted so that the columns have been removed. Each student's record simply contains a single string of digits. Knowing that the string of digits must have come from G different assignments (each with a possible integer grade between 0 and 100, inclusive), parse the string so that the average of the G grades is maximized. No grade other than 0 will start with the digit 0 (i.e. there are no leading zeros in any grade). Print out the average for the given grades, rounded to the nearest integer.

Input

The first line of input contains the number of test cases, C (1 <= C <= 100). Each of the following C lines contains an integer G (1 <= G <= 25) indicating the number of grades, followed by a string of digits containing the corrupted grades.

Output

For each test case, output a single line containing the maximum average grade possible.

Sample Input

Sample Output

44
5
100