Large Refrigerator

## 题目描述 $t$ 组数据。给定长方体的体积 $V$（以质因子乘积的形式给出），找到 $3$ 个正整数 $a,b,c$，使得 $V = abc$，且长方体的表面积 $S = 2(ab + bc + ac)$ 尽可能小。 ## 输入输出格式 **输入格式：** 第一行包含一个正整数 $t$，表示数据组数。 对于每组数据，第一行包含一个正整数 $k$，表示 $V$ 有 $k$ 个质因子。 接下来 $k$ 行，每行包含两个正整数 $p_i$ 和 $a_i$，且 $V = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ **输出格式：** 对于每组询问，按顺序输出 $S,a,b,c$，中间用空格分开，如果有多个 $a,b,c$ 符合条件，输出任意一种方案即可（$a,b,c$ 无须有序）。 ## 说明 $1 \leq t \leq 500,2 \leq V \leq 10^{18},p_i \in {\rm prime}$，所有 $p_i$ 互不相同。

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.

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<=10^{18} $ ), 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}&gt;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.

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

In the first data set of the sample the fridge's volume $ V=2^{3}=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.