#A2. NOI online 2022 普及组第二题

NOI online 2022 普及组第二题

题目描述

Kri 喜欢玩数字游戏。

一天,他在草稿纸上写下了 tt 对正整数 (x,y)(x,y),并对于每一对正整数计算出了 z=x×y×gcd(x,y)z=x×y×gcd(x,y)

可是调皮的 Zay 找到了 Kri 的草稿纸,并把每一组的 yy 都擦除了,还可能改动了一些 zz

现在 Kri 想请你帮忙还原每一组的 yy,具体地,对于每一组中的 xxzz,你需要输出最小的正整数 yy,使得 z=x×y×gcd(x,y)z=x×y×gcd(x,y)。如果这样的 yy 不存在,也就是 Zay 一定改动了 zz,那么请输出1−1

注:gcd(x,y)gcd(x,y) 表示 xxyy 的最大公约数,也就是最大的正整数 dd,满足 dd 既是 xx 的约数,又是 yy 的约数。

输入格式

第一行一个整数 ,表示有 tt 对正整数 xxzz

接下来 tt 行,每行两个正整数 xxzz,含义见题目描述。

输出格式

对于每对数字输出一行,如果不存在满足条件的正整数 yy,请输出 1−1,否则输出满足条件的最小正整数 yy

1
10 240
12
3
5 30
4 8
11 11
6
-1
1

数据规模与约定

对于 20%20\% 的数据,t,x,z103t,x,z≤10^3

对于 40%40\% 的数据,t103t≤10 ^3x106x≤10^ 6z109z≤10^ 9

对于另 30%30\%的数据,t104t≤10^ 4

对于另 20%20\% 的数据,x106x≤10^ 6

对于 100%100\% 的数据,1t5×1051≤t≤5×10^ 51x1091≤x≤10^ 91z<2631≤z<2^{63}