← 返回题目列表

Codeforces · 1506/A

A. 奇怪的桌子

中文机器翻译题面 查看原题

Polycarp 发现了一个由 $$$n$$$ 行和 $$$m$$$ 列组成的矩形表格。他注意到表格的每个单元格都有其编号,通过以下算法“按列”获得:

- 单元格从 1 开始编号;
- 单元格按列从左到右编号,每列内部从上到下编号;
- 每个单元格的编号是比前一个单元格大一的整数。

例如,如果 $$$n = 3$$$ 且 $$$m = 5$$$,则表格将按如下方式编号:

$$$$$$ \begin{矩阵} 1 & 4 & 7 & 10 & 13 \\ 2 & 5 & 8 & 11 & 14 \\ 3 & 6 & 9 & 12 & 15 \\ \end{矩阵} $$$$$$

然而,Polycarp 认为这样的编号不方便。他喜欢“按行”编号:

- 单元格从 1 开始编号;
- 单元格从上到下按行编号,每行内部从左到右;
- 每个单元格的编号是比前一个单元格的编号大一的整数。

例如,如果 $$$n = 3$$$ 且 $$$m = 5$$$,则 Polycarp 喜欢以下表格编号: $$$$$$ \begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 6 & 7 & 8 & 9 & 10 \\ 11 & 12 & 13 & \\ 14 & 15 \end{矩阵} $$$$$$

Polycarp 没有太多时间,所以他要求你找出“按行”编号中的单元格编号是多少,如果“按列”编号中单元格的编号为 $$$x$$$?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$)。然后是 $$$t$$$ 测试用例。

每个测试用例由一行包含三个整数 $$$n$$$、$$$m$$$、$$$x$$$ ($$$1 \le n, m \le 10^6$$$, $$$1 \le x \le n \cdot m$$$) 组成,其中 $$$n$$$ 和 $$$m$$$ 是表中的行数和列数,并且$$$x$$$ 是单元格编号。

请注意,某些测试用例中的数字不适合 $$$32$$$ 位整数类型,因此您必须至少使用编程语言的 $$$64$$$ 位整数类型。

输出

对于每个测试用例,输出“按行”编号中的单元格编号。

示例

输入 #1

5
1 1 1
2 2 3
3 5 11
100 100 7312
1000000 1000000 1000000000000

输出 #1

1
2
9
1174
1000000000000