[BPOJ-R2E]Prime
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
小 非常喜欢数学,他想出了一道题,但是他并不会解,请你来帮他解决。
有 组输入,每组给出一个整数 和 个整数 ,请你找到最小的整数 (),使得 ,其中 。也就是说使得 与任意的 互质。
注: 表示求 和 的最大公约数。
输入格式
第一行一个整数 ,表示有 组输入。
接下来 组输入,每组第一行为一个整数 ,第二行为 个整数。
输出格式
对于每组输入,输出一个整数 ,且 ,表示满足要求的答案。
样例输入输出
3
3
5 7 25
4
1 2 3 4
1
2
2
5
3
说明/提示
【样例解释 #1】
对于第一组输入, 满足 ,且 为最小答案。
对于 的数据,满足 ,,。