#530. 「LibreOJ β Round #5」最小倍数

内存限制:256 MiB 时间限制:900 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: tangjz

题目描述

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

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

给定 pp,求最小的正整数 nn,使得 n!modp=0n! \bmod p = 0

由于 pp 很大,输入将给出 mme1,e2,,eme_1, e_2, \cdots, e_m,表示 p=i=1mprieip = \prod_{i = 1}^{m}{\mathrm{pr}_i^{e_i}},其中 pri\mathrm{pr}_i 是从小到大第 ii 个质数。

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

输入格式

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

每组数据第一行一个正整数 mm

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

输出格式

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

样例

样例输入 1

1
5
1 1 1 1 1

样例输出 1

11

样例解释 1

2×3×5×7×11=23102 \times 3 \times 5 \times 7 \times 11 = 2310,最小可能的 nn1111

样例输入 2

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

样例输出 2

666

样例解释 2

本来有一个绝妙的解释,但是这里太小,写不下。

数据范围与提示

ai=priei(i=1,2,,m)a_i = \mathrm{pr}_i \cdot e_i(i = 1, 2, \cdots, m)

对于所有数据,1T104,1m100,0ai10181\leq T \leq 10^4, 1 \leq m \leq 100, 0 \leq a_i \leq 10^{18}

Subtask # 分值 TT 的限制 aa 的限制
1 1010 T=1T = 1 ai105a_i \leq 10^5
2 2525 T103T \leq 10^3 ai106a_i \leq 10^6
3 3030 T103T \leq 10^3 ai1018a_i \leq 10^{18}
4 3535 T104T \leq 10^4 ai1018a_i \leq 10^{18}