样例下载

题目描述

给出一个整数 m，解方程 x! % m = 0。其中 ! 表示阶乘，% 表示取模。

方程的解可能很多，你只需要输出最小的正整数解。

由于给出的 m 可能很大，输入不直接给出 m 的值，而是给出 m 的唯一分解式，即给出一个整数 k 和 k 个整数 $c_1, c_2, ……, c_k$，表示 $m = \prod_{i = 1}^{k}{p_i^{c_i}}$，其中 $p_i$ 是从小到大第 $i$ 个质数。

多组数据。

输入格式

第一行：包含一个整数 T, 表示数据组数。

对于每组数据：

• 第一行：包含一个整数 k；
• 第二行：包含 k 个非负整数 $c_i (i = 1, 2, ……, k)$

输出格式

共 T 行，每组数据的答案占一行。

样例输入

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

样例输出

11
666

样例解释

此处仅解释第一组数据：

m = 2 × 3 × 5 × 7 × 11 = 2310

x 的最小正整数解是 11。

数据范围

设 $a_i = p_i × c_i (i = 1, 2, ……, k)$。

100% 的数据：$1 ≤ T ≤ 10^4, 1 ≤ k ≤ 100, 0 ≤ a_i ≤ 10^{18}$。