You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

第二天，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

1
5
1 1 1 1 1

11

$2 \times 3 \times 5 \times 7 \times 11 = 2310$，最小可能的 $n$ 是 $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}$。

Subtask #	分值	$T$ 的限制	$a$ 的限制
1	$10$	$T = 1$	$a_i \leq 10^5$
2	$25$	$T \leq 10^3$	$a_i \leq 10^6$
3	$30$		$a_i \leq 10^{18}$
4	$35$	$T \leq 10^4$