题目描述

第二天，LCR 终于启动了备份存储器，准备上传数据时，却没有找到熟悉的文件资源，取而代之的是而屏幕上显示的一段话：

您的文件存在被盗风险，为安全起见，您需要通过「智商·身份验证 ver. 5.0 β 版」的验证，以证明您是资料的主人。请写一个程序解决下述问题：

给定 $p$，求最小的正整数 $n$，使得 $n! \bmod p = 0$。

由于 $p$ 很大，输入将给出 $m$ 和 $e_1, e_2, \cdots, e_m$，表示 $p = \prod_{i = 1}^{m}{\mathrm{pr}_i^{e_i}}$，其中 $\mathrm{pr}_i$ 是从小到大第 $i$ 个质数。

一共有 $T$ 个同样形式的问题需要解决。

输入格式

第一行包含一个正整数 $T$ 表示数据组数。

每组数据第一行一个正整数 $m$ 。

第二行包含 $m$ 个非负整数，其中第 $i$ 个数字表示 $e_i(i = 1, 2, \cdots, m)$ ，相邻两个数字之间恰好有一个空格。

输出格式

输出共 $T$ 行，每行包含一个数字，表示该组数据的答案。

1
5
1 1 1 1 1

11

1
12
1 3 4 6 7 9 10 12 13 15 16 18

666

数据范围与提示

设 $a_i = \mathrm{pr}_i \cdot e_i(i = 1, 2, \cdots, m)$。

对于所有数据，$1\leq T \leq 10^4, 1 \leq m \leq 100, 0 \leq a_i \leq 10^{18}$。