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

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

题目描述

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

样例输出 1

11

样例解释 1

2 \times 3 \times 5 \times 7 \times 11 = 2310 ,最小可能的 n 11

样例输入 2

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

样例输出 2

666

样例解释 2

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

数据范围与提示

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