CF163D.Large Refrigerator

Vasya wants to buy a new refrigerator. He believes that a refrigerator should be a rectangular parallelepiped with integer edge lengths. Vasya calculated that for daily use he will need a refrigerator with volume of at least V. Moreover, Vasya is a minimalist by nature, so the volume should be no more than V, either — why take up extra space in the apartment? Having made up his mind about the volume of the refrigerator, Vasya faced a new challenge — for a fixed volume of V the refrigerator must have the minimum surface area so that it is easier to clean.

The volume and the surface area of a refrigerator with edges a, b, c are equal to V = abc and S = 2(ab + bc + ca), correspondingly.

Given the volume V, help Vasya find the integer lengths for the refrigerator's edges a, b, c so that the refrigerator's volume equals V and its surface area S is minimized.

瓦西里想买一台新冰箱。他认为冰箱应该是一个长、宽、高均为整数的长方体。瓦西里计算得出，为满足日常使用需求，冰箱的体积至少应为 $V$。此外，瓦西里天性崇尚极简主义，因此冰箱体积也不应超过 $V$——何必在公寓里占用额外空间呢？在确定了冰箱体积必须恰好为 $V$ 后，瓦西里又面临一项新挑战：在体积固定为 $V$ 的前提下，冰箱的表面积需尽可能小，以便于清洁。

对于边长分别为 $a$、$b$、$c$ 的冰箱，其体积和表面积分别为 $V = abc$ 和 $S = 2(ab + bc + ca)$。

给定体积 $V$，请帮助瓦西里找出满足体积恰好为 $V$ 且表面积 $S$ 最小的整数边长 $a$、$b$、$c$。

The first line contains a single integer t (1 ≤ t ≤ 500) — the number of data sets.

The description of t data sets follows. Each set consists of a single integer V (2 ≤ V ≤ 1018), given by its factorization as follows.

Let V = _p_1_a_1_p_2_a_2... p__k__a__k, where p__i are different prime numbers and a__i are positive integer powers.

Then the first line describing a data set contains a single positive integer k — the number of different prime divisors of V. Next k lines contain prime numbers p__i and their powers a__i, separated by spaces. All p__i are different, all a__i > 0.

第一行包含一个整数 $t$（$1 \leq t \leq 500$）—— 数据组数。

接下来是 $t$ 组数据的描述。每组数据由一个整数 $V$（$2 \leq V \leq 10^{18}$）给出，其以质因数分解形式表示如下：

设 $V = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}$，其中 $p_i$ 是互不相同的质数，$a_i$ 是正整数指数。

则描述每组数据的第一行包含一个正整数 $k$ —— $V$ 的不同质因子个数。接下来的 $k$ 行中，每行包含一个质数 $p_i$ 及其对应的指数 $a_i$，两者以空格分隔。所有 $p_i$ 互不相同，且所有 $a_i > 0$。

Print t lines, on the i-th line print the answer to the i-th data set as four space-separated integers: the minimum possible surface area S and the corresponding edge lengths a, b, c. If there are multiple variants of the lengths of edges that give the minimum area, you are allowed to print any of them. You can print the lengths of the fridge's edges in any order.

输出 t 行，第 i 行输出第 i 个数据集的答案，即四个以空格分隔的整数：最小可能的表面积 S 及其对应的棱长 a、b、c。若存在多种能取得最小表面积的棱长组合，任选其中一种输出即可。冰箱三条棱的长度顺序可以任意。

In the first data set of the sample the fridge's volume V = 23 = 8, and the minimum surface area will be produced by the edges of equal length.

In the second data set the volume V = 17, and it can be produced by only one set of integer lengths.

在样例的第一组数据中，冰箱的体积 $V = 23 = 8$，此时当三条棱长均相等时，表面积最小。

在样例的第二组数据中，体积 $V = 17$，且仅能由唯一一组整数棱长构成。