Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

E. Плитка шоколада
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть плитка шоколада, состоящая из n × m долек. Вы хотите съесть ровно k долек, для этого может потребоваться разделить шоколадку на части.

За одно действие можно разломить ровно один цельный прямоугольный кусок шоколада на два прямоугольных куска. Разламывать можно только по линиям, проходящим между дольками: по горизонтали или по вертикали. Стоимость разлома равна квадрату длины разлома.

Например, если сначала у вас была шоколадка из 2 × 3 долек, то за один горизонтальный разлом вы можете получить два цельных куска 1 × 3 (стоимость такого разлома равна 32 = 9), либо вы можете разломить шоколадку по вертикали одним из двух способов и получить два цельных куска 2 × 1, 2 × 2 (стоимость такого разлома равна 22 = 4).

Ваша задача для нескольких значений n, m и k определить, за какую минимальную суммарную стоимость разломов, можно разделить исходную шоколадку на такие прямоугольные куски, что можно выбрать несколько кусков, суммарный размер которых составляет ровно k долек. При этом оставшиеся n·m - k долек не обязательно образуют цельный кусок.

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

В первой строке находится целое положительное число t (1 ≤ t ≤ 40910) — количество троек n, m и k, для которых нужно решить задачу.

В следующих t строках записаны по три целых числа n, m и k (1 ≤ n, m ≤ 30, 1 ≤ k ≤ min(n·m, 50)) — размеры очередной шоколадки и количество её долек, которые вы хотите съесть.

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

Для каждой тройки n, m и k выведите минимальную стоимость, которую необходимо потратить на разламывание шоколадки, чтобы можно было съесть ровно k долек.

Примеры
Входные данные
4
2 2 1
2 2 3
2 2 2
2 2 4
Выходные данные
5
5
4
0
Примечание

В первом запросе из примера необходимо сделать два разлома:

  • сначала нужно разбить кусок размера 2 × 2 на два куска размера 2 × 1 (стоимость такого разлома равна 22 = 4),
  • затем нужно один из получившихся кусков размера 2 × 1 разломить на два куска размера 1 × 1 (стоимость такого разлома равна 12 = 1).

Во втором запросе из примера вы хотите съесть 3 дольки. Для этого можно действовать аналогично первому запросу.