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,并且它只能由一组整数长度产生。