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