A国共有n种不同面额的货币,第i种货币的面额为。为了方便,我们把货币种数为、面额数组为的货币系统记作。
但A国的货币系统可能是不完善的,即可能存在金额x不能被该货币系统表示出。例如在货币系统中,金额1,3就无法被表示出来。
两个货币系统和是等价的,当且仅当对于任意非负整数,它要么均可以被两个货币系统表示出,要么不能被其中任何一个表示出。
琳琳希望找到一个货币系统,满足与原来的货币系统等价,且尽可能的小。你可以帮助她找到最小的吗?
输入文件的第一行包含一个整数,表示数据的组数。
随后每组数据的第一行包含一个正整数,接下来一行包含个由空格隔开的正整数。
输出文件共有 行,对于每组数据,输出一行一个正整数,表示所有与等价的货币系统中,最小的。
2 4 3 19 10 6 5 11 29 13 19 17
2 5
在第一组数据中,货币系统和给出的货币系统等价,并可以验证不存在的等价的货币系统,因此答案为。
在第二组数据中,可以验证不存在的等价的货币系统,因此答案为。
。
时间限制 | 1 秒 |
内存限制 | 128 MB |