Corrupted Gradebook

시간 제한1초메모리 제한1024 MB

요약

숫자 문자열을 정확히 G개의 성적으로 나누되 앞에 0이 오지 않게 하여 평균을 최대로 만든다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 문자열, 그리디
정답자: 아직 제출이 없습니다

문제

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.

입력

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.

출력

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

예제1

예제 1
입력
```
3
2 835
2 100
1 100
```
예상 출력
```
44
5
100
```