This page is still under construction.

Parts of this page are still being built. What you see may change.

ACM Hotel

Time limit1sMemory limit256 MB

Summary
Guests fill rooms column by column from the elevator with lower floors first, so print the room number of the Nth guest.
Level

Easy1 of 10

Topics
Math
Solved
No attempts yet

Problem

Jiwoo manages the ACM Hotel and gives each guest an empty room as the guest arrives. A survey says that guests prefer the room with the shortest walking distance from the hotel entrance. Write a program that assigns rooms by that result.

To keep the problem simple, assume the hotel is a rectangle. It has HH floors with WW rooms on every floor, and the elevator is at the far left. A hotel of this shape is called an H×WH \times W hotel. The entrance is right in front of the elevator on floor 1, and the distance from the entrance to the elevator is ignored. Every two adjacent rooms are at distance 1, and rooms exist only along the front of the hotel.

A room number has the form YXXYXX or YYXXYYXX. YY or YYYY is the floor, and XXXX is the position counted from the elevator. For example, the fifth room from the elevator on floor 3 is room 305.

A guest does not care how far the elevator travels. When the walking distance is the same, a guest prefers the lower floor. Room 301 is preferred over room 102, because room 102 needs a walk of distance 2 while room 301 needs a walk of distance 1. For the same reason room 2101 is preferred over room 102.

Every room is empty at the start. Find the room number given to the NNth guest under this policy. The first guest takes room 101 and the second guest takes room 201. In a hotel with H=6H = 6 and W=12W = 12, the 10th guest takes room 402.

Input

The first line has the number of test data TT. Each of the next TT lines has three integers HH, WW, NN, in that order the number of floors, the number of rooms on each floor, and which guest to place (1≤H,W≤991 \le H, W \le 99, 1≤N≤H×W1 \le N \le H \times W).

Output

For each test data, print the room number given to the NNth guest on one line.

Examples5

  1. Example 1

    Input
    2
6 12 10
30 50 72
    Expected output
    402
1203

  2. Example 2

    Input
    1
1 1 1
    Expected output
    101

  3. Example 3

    Input
    4
6 12 1
6 12 6
6 12 7
6 12 12
    Expected output
    101
601
102
602

  4. Example 4

    Input
    3
1 99 1
1 99 50
1 99 99
    Expected output
    101
150
199

  5. Example 5

    Input
    3
99 1 1
99 1 50
99 1 99
    Expected output
    101
5001
9901