ponork 세기

회의의 핵심 일정이 총회 금융 센터(KFC)에서 열렸으니 이 건물은 제대로 지켜야 했다. 낮에는 직접 본 사람도 많겠지만 경비가 넘칠 만큼 촘촘했다. 여기서 다룰 시간은 시위대까지 대부분 잠자리에 든 평범한 밤이다.

밤에도 건물을 지켜야 한다. 이 일은 특별 훈련을 받은 경비원 몇 명이 맡아 밤새 서로 다른 경로로 KFC 둘레를 돈다. 그중 가장 중요한 경로는 건물 전체를 감싸는 좁은 담을 따라간다. 담 위에서는 주변이 아주 잘 보여서 전략상 이 경로를 골랐다. 주변을 빠짐없이 살피려면 경비원 여러 명을 이 경로에 배치해야 하는데, 쓸 수 있는 인원은 늘 필요한 수보다 적다. 그래서 경찰 지휘부는 건물 주변을 계속 시야에 두면서도 가장 적은 인원으로 해내는 방법을 찾아야 한다. 그러려면 먼저 경로가 얼마나 길고 경비원이 그 경로를 도는 데 얼마나 걸리는지 알아야 한다. 그 길이를 재는 일이 이번 문제다.

경찰은 경로의 길이를 잴 때 경찰 표준 걸음, 줄여서 ponork를 단위로 쓴다. 담은 직선 구간이 직각으로 이어진 모양이고, 구간 하나의 길이는 1 ponork 이상이다. 경찰 규정에 따르면 담 위를 걷는 경비원은 방향이 바뀌어도 보폭을 줄이지 않고 모퉁이를 넘어 디디며, 한 걸음의 길이는 언제나 정확히 1 ponork다. 즉 한 걸음은 발을 디딘 자리에서 다음에 디딜 자리까지의 직선 거리가 정확히 1 ponork인 이동이고, 모퉁이에서는 담을 따라 꺾이지 않고 직선으로 질러간다. 담의 두께는 0으로 본다. 마지막 걸음이 담의 끝점에 정확히 떨어지도록 경로를 걸을 수 없으면, 남은 거리는 1 ponork의 절반 이상일 때만 한 걸음으로 센다. 담을 따라가는 경로의 길이를 ponork 단위로 구하여라. 그림은 예제 입력의 첫 번째 테스트 케이스에 해당한다.

첫 줄에 양의 정수 $Z$가 주어지고, 이어서 테스트 케이스 $Z$개가 차례로 주어진다. 각 테스트 케이스의 첫 줄에는 두 값 $K$와 $U$가 주어진다($1 \le K < 1000$, $1 \le U < 5000$). $K$는 경비원의 보폭, 곧 1 ponork의 크기이고, $U$는 담을 이루는 구간의 개수다. 다음 $U$개의 줄에는 각 구간의 길이가 한 줄에 하나씩 주어진다. 모든 길이는 $K$ 이상인 정수다.

각 테스트 케이스마다 Strazny ujde X ponorku. 형식으로 정확히 한 줄씩 출력한다. $X$는 담 전체를 지나는 데 필요한 걸음 수다. 문장은 보인 그대로 쓰고 $X$ 자리에만 값을 넣는다.