There is a ball at the top-left corner of an n \times m grid. The rows of the grid are numbered 1,2,\dots,n, and the columns are numbered 1,2,\dots,m.

The ball is initially moving diagonally away from the top-left corner. At every step, it moves one cell. Whenever the ball hits the border of the grid, it changes its direction.

What is the location of the ball after k steps and how many times has it changed direction?

Input

The first line has an integer t: the number of tests.

After this, there are t lines. Each line has three integers n, m and k: the size of the grid and the number of steps.

Output

For each test, print three integers: the location of the ball and the number of direction changes.

Constraints

• 1 \le t \le 1000
• 2 \le n,m \le 10^9
• 0 \le k \le 10^{18}

Example

Input:

6
3 4 0
3 4 1
3 4 2
3 4 3
3 4 4
42 1337 123456789

Output:

1 1 0
2 2 0
3 3 1
2 4 2
1 3 3
34 300 3101295