ACM 호텔

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

요약

엘리베이터에서 가까운 방부터 아래층 순서로 채워 N번째 손님이 배정받는 호실을 출력합니다.

난이도: 쉬움10점 중 1점
유형: 수학
정답자: 아직 제출이 없습니다

문제

호텔 매니저 지우는 손님이 도착하는 대로 빈 방을 배정한다. 설문조사 결과 손님은 호텔 정문에서 걸어가는 거리가 가장 짧은 방을 선호한다고 한다. 이 결과대로 방을 배정하는 프로그램을 작성하자.

문제를 단순하게 만들기 위해 호텔이 직사각형이라고 하자. 각 층에 $W$ 개의 방이 있는 $H$ 층 건물이고, 엘리베이터는 가장 왼쪽에 있다. 이런 모양의 호텔을 $H \times W$ 호텔이라고 부른다. 호텔 정문은 1층 엘리베이터 바로 앞에 있고, 정문에서 엘리베이터까지의 거리는 무시한다. 인접한 두 방 사이의 거리는 모두 1이고, 방은 호텔 정면 쪽에만 있다.

방 번호는 $YXX$ 또는 $YYXX$ 형태다. $Y$ 나 $YY$ 는 층수이고, $XX$ 는 엘리베이터에서부터 센 번호다. 예를 들어 3층에서 엘리베이터부터 다섯 번째 방은 305호다.

손님은 엘리베이터를 타고 이동하는 거리는 신경 쓰지 않는다. 다만 걷는 거리가 같으면 아래층 방을 더 선호한다. 102호보다 301호를 더 선호하는데, 102호는 거리 2만큼 걸어야 하지만 301호는 거리 1만 걸으면 되기 때문이다. 같은 이유로 102호보다 2101호를 더 선호한다.

처음에는 모든 방이 비어 있다. 이 방침에 따라 $N$ 번째로 도착한 손님에게 배정되는 방 번호를 구한다. 첫 번째 손님은 101호, 두 번째 손님은 201호에 들어간다. $H = 6$ , $W = 12$ 인 호텔이라면 10번째 손님은 402호에 들어간다.

입력

첫 줄에 테스트 데이터의 개수 $T$ 가 주어진다. 이어지는 $T$ 개의 줄에는 각각 세 정수 $H$ , $W$ , $N$ 이 주어지며 순서대로 호텔의 층수, 각 층의 방 수, 몇 번째 손님인지를 나타낸다 ( $1 \le H, W \le 99$ , $1 \le N \le H \times W$ ).

출력

각 테스트 데이터마다 $N$ 번째 손님에게 배정할 방 번호를 한 줄에 출력한다.

예제5

예제 1
입력
```
2
6 12 10
30 50 72
```
예상 출력
```
402
1203
```
예제 2
입력
```
1
1 1 1
```
예상 출력
```
101
```

예제 3

입력

예상 출력

예제 4
입력
```
3
1 99 1
1 99 50
1 99 99
```
예상 출력
```
101
150
199
```
예제 5
입력
```
3
99 1 1
99 1 50
99 1 99
```
예상 출력
```
101
5001
9901
```