D. Большой холодильник
ограничение по времени на тест
5 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Вася хочет купить новый холодильник. Он считает, что холодильник должен быть прямоугольным параллелепипедом с целочисленными длинами ребер. Вася рассчитал, что для повседневного пользования ему понадобится холодильник объема не меньше V. Кроме того, Вася по натуре минималист, поэтому объем должен быть и не больше V — к чему занимать лишнее место в квартире? Определившись с объемом холодильника, Вася столкнулся с новой непростой задачей — чтобы холодильник было проще мыть, при фиксированном объеме V он должен иметь минимальную площадь поверхности.

Объем и площадь поверхности холодильника с ребрами a, b, c равны V = abc и S = 2(ab + bc + ca), соответственно.

Помогите Васе по заданному объему V найти такие целые длины ребер холодильника a, b, c, чтобы объем холодильника был равен V и при этом его площадь поверхности S была минимальна.

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

В первой строке записано единственное целое число t (1 ≤ t ≤ 500) — количество наборов данных.

Далее следует описание t наборов данных. Каждый набор состоит из одного целого числа V (2 ≤ V ≤ 1018), заданного своим разложением на множители следующим образом.

Пусть V = p1a1p2a2... pkak, где pi — различные простые числа, а ai — положительные целые степени.

Тогда в первой строке описания набора данных записано единственное положительное целое число k — количество различных простых делителей V. В следующих k строках записаны простые числа pi и их степени ai, разделенные пробелом. Все pi различны, все ai > 0.

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

Выведите t строк, в i-й строке выведите ответ на i-й набор данных — четыре целых числа, записанные через пробел: минимальная возможная площадь поверхности S и соответствующие длины ребер a, b, c. Если вариантов длин ребер, дающих минимальную площадь, несколько, разрешается вывести любой из них. Длины ребер холодильника разрешается выводить в любом порядке.

Примеры
Входные данные
3
1
2 3
1
17 1
3
3 1
2 3
5 1
Выходные данные
24 2 2 2
70 1 1 17
148 4 6 5
Примечание

В первом наборе данных примера объем холодильника V = 23 = 8, и минимальную площадь поверхности дадут ребра одинаковой длины.

Во втором наборе данных объем V = 17, и его можно получить из единственного набора ребер целочисленных длин.