黑妹又开始玩起了一个游戏，这次她面对的是一个序列，序列里的每个数字都是正整数，黑妹每次可以从这个序列里选择两个数字，然后将这两个数字除以它们任意一个公共因子。 如果 x 是 a 和 b 的公共因子，当且仅当 a 和 b 都能被 x 整除。 黑妹很快玩腻了这些操作，她现在想知道，这个序列经过一些操作之后，将新序列的每个元素都乘起来的最小乘积是多少，由于这个乘积可能很大，所以你需要告诉黑妹这个乘积对109+7取模之后的值。

输入描述:

第一行一个整数T表示数据的组数。(1 ≤ T ≤ 10)对于每组数据：第一行n表示序列的长度。(1 ≤ n ≤ 10000)接下来一行n个整数ai表示序列的每个元素。(1 ≤ ai ≤ 108)

输出描述:

对于每组数据输出一行表示答案。