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