← 返回题目列表

Codeforces · 163/D

D. 大型冰箱

中文机器翻译题面 查看原题

Vasya 想买一台新冰箱。他认为冰箱应该是一个边长为整数的长方体。 Vasya计算了一下,日常使用至少需要一台容积为V的冰箱。而且,Vasya生性极简,所以容积也不能超过V——何必多占公寓的空间呢?确定了冰箱的体积后,Vasya 面临着新的挑战——对于固定体积的 V,冰箱必须具有最小的表面积,以便更容易清洁。

具有 a、b、c 边的冰箱的体积和表面积分别等于 V = abc 和 S = 2(ab + bc + ca)。

给定体积 V,帮助 Vasya 找到冰箱边缘 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。如果提供最小面积的边缘长度有多种变体,则允许打印其中任何一种。您可以按任意顺序打印冰箱边缘的长度。

示例

输入 #1

3
1
2 3
1
17 1
3
3 1
2 3
5 1

输出 #1

24 2 2 2
70 1 1 17
148 4 6 5

注意

在样本的第一个数据集中,冰箱的体积 V = 23 = 8,最小表面积将由相等长度的边缘产生。

在第二个数据集中,体积 V = 17,并且它只能由一组整数长度产生。