#1846. NOI online 2022 普及组第二题
NOI online 2022 普及组第二题
题目描述
Kri 喜欢玩数字游戏。
一天,他在草稿纸上写下了 对正整数 ,并对于每一对正整数计算出了
可是调皮的 Zay 找到了 Kri 的草稿纸,并把每一组的 都擦除了,还可能改动了一些 。
现在 Kri 想请你帮忙还原每一组的 ,具体地,对于每一组中的 和 ,你需要输出最小的正整数 ,使得 。如果这样的 不存在,也就是 Zay 一定改动了 ,那么请输出。
注: 表示 和 的最大公约数,也就是最大的正整数 ,满足 既是 的约数,又是 的约数。
输入格式
第一行一个整数 ,表示有 对正整数 和 。
接下来 行,每行两个正整数 和 ,含义见题目描述。
输出格式
对于每对数字输出一行,如果不存在满足条件的正整数 ,请输出 ,否则输出满足条件的最小正整数 。
1
10 240
12
3
5 30
4 8
11 11
6
-1
1
数据规模与约定
对于 的数据, 。
对于 的数据, , , 。
对于另 的数据, 。
对于另 的数据, 。
对于 的数据, ,, 。