D. Игра с бумагой
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Чтобы скоротать время в долгой поездке, Айзат придумала следующую игру.

В начале игры у Айзат есть клетчатый лист бумаги размером $$$W$$$ клеток в ширину и $$$H$$$ клеток в высоту (всего $$$W \times H$$$ клеток).

За один ход Айзат может разорвать лист на две части по границе клеток (по вертикали или по горизонтали). Из двух получившихся листов Айзат оставляет в игре лист с большим количеством клеток.

Айзат интересуется, за какое минимальное количество ходов она сможет получить лист, на котором будет не более чем $$$S$$$ клеток.

Входные данные

В первой строке находится единственное целое число $$$T$$$ $$$(1 \le T \le 10^3)$$$ — количество игр, в которые Айзат успеет сыграть в поездке.

Следующие $$$T$$$ строк содержат через пробел три целых числа $$$W_i$$$, $$$H_i$$$, $$$S_i$$$ $$$(1 \le W_i, H_i \le 10^9; 1 \le S_i \le 10^{18})$$$ — количество клеток в ширину и высоту на $$$i$$$-м листе, а также верхняя граница для количества клеток в конце $$$i$$$-й игры.

Выходные данные

Выведите через пробел $$$T$$$ чисел $$$D_i$$$ — минимальное количество ходов, необходимое для того, чтобы из листа размером $$$W_i \times H_i$$$ клеток получился лист, содержащий не более $$$S_i$$$ клеток.

Примеры
Входные данные
3
3 25 2
6 6 50
9 7 19
Выходные данные
6 0 2
Входные данные
4
123456789 567891234 912345678
912345678 123456789 567891234
567891234 912345678 123456789
987654321 876543219 123456789123456789
Выходные данные
27 28 32 3
Примечание

Первый тестовый пример

Айзат сыграет в три игры:

  1. Из листа размером $$$3 \times 25$$$ можно получить лист размером не более чем в $$$2$$$ клетки, например, следующим образом:
    • $$$3 \times 25$$$ $$$\rightarrow$$$ $$$3 \times 14$$$ (отбросили $$$3 \times 11$$$);
    • $$$3 \times 14$$$ $$$\rightarrow$$$ $$$3 \times 7$$$ (отбросили $$$3 \times 7$$$);
    • $$$3 \times 7$$$ $$$\rightarrow$$$ $$$3 \times 4$$$ (отбросили $$$3 \times 3$$$);
    • $$$3 \times 4$$$ $$$\rightarrow$$$ $$$2 \times 4$$$ (отбросили $$$1 \times 4$$$);
    • $$$2 \times 4$$$ $$$\rightarrow$$$ $$$2 \times 2$$$ (отбросили $$$2 \times 2$$$);
    • $$$2 \times 2$$$ $$$\rightarrow$$$ $$$1 \times 2$$$ (отбросили $$$1 \times 2$$$).

    Возможны и другие варианты ходов, но быстрее, чем за шесть ходов получить лист из $$$2$$$ или менее клеток нельзя.

  2. Лист размером $$$6 \times 6$$$ содержит $$$36$$$ клеток, что уже меньше, чем $$$50$$$. Поэтому игра заканчивается без единого разрыва.
  3. Лист размером $$$9 \times 7$$$ можно привести к листу из $$$18 \le 19$$$ клеток следующим образом:
    • $$$9 \times 7$$$ $$$\rightarrow$$$ $$$9 \times 4$$$ (отбросили $$$9 \times 3$$$);
    • $$$9 \times 4$$$ $$$\rightarrow$$$ $$$9 \times 2$$$ (отбросили $$$9 \times 2$$$).

    Можно показать, что никакая другая последовательность из двух ходов не может привести к листу, содержащему не более 19 клеток.