Олимпиадный тренинг

Задача . A. Странная таблица


Задача

Темы: математика *800

Поликарп нашел прямоугольную таблицу, состоящую из \(n\) строк и \(m\) столбцов. Он заметил, что в каждой ячейке таблицы записан ее номер, полученный по следующему алгоритму «по столбцам»:

  • ячейки занумерованы начиная с единицы;
  • ячейки нумеруются слева направо по столбцам, а внутри каждого столбца сверху вниз;
  • номер каждой ячейки — целое число, на единицу большее, чем номер предыдущей ячейки.

Например, если \(n = 3\) и \(m = 5\), то таблица будет занумерована следующим образом:

\(\) \begin{matrix} 1 & 4 & 7 & 10 & 13 \\ 2 & 5 & 8 & 11 & 14 \\ 3 & 6 & 9 & 12 & 15 \\ \end{matrix} \(\)

Однако, Поликарп считает такую нумерацию неудобной. Ему нравится нумерация «по строкам»:

  • ячейки занумерованы начиная с единицы;
  • ячейки нумеруются сверху вниз по строкам, а внутри каждой строки слева направо;
  • номер каждой ячейки — целое число, на единицу большее, чем номер предыдущей ячейки.

Например, если \(n = 3\) и \(m = 5\), то Поликарпу нравится следующая нумерация таблицы: \(\) \begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 6 & 7 & 8 & 9 & 10 \\ 11 & 12 & 13 & 14 & 15 \\ \end{matrix} \(\)

У Поликарпа мало времени, поэтому он просит вас узнать, какой был бы номер ячейки в нумерации «по строкам», если в нумерации «по столбцам» ячейка имеет номер \(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
2
9
1174
1000000000000

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя