题目描述

Kri 喜欢玩数字游戏。

一天，他在草稿纸上写下了 $t$ 对正整数 ($x$,$y$)，并对于每一对正整数计算出了

$z = x × y × gcd(x,y)$ 。

可是调皮的 Zay 找到了 Kri 的草稿纸，并把每一组的 $y$ 都擦除了，还可能改动了一些 $z$ 。

现在 Kri 想请你帮忙还原每一组的 $y$ ，具体地，对于每一组中的 $x$ 和 $z$ ，你需要输出最小的正整数 $y$ ，

使得 $z = x × y × gcd(x,y)$ 。如果这样的 $y$ 不存在，也就是 Zay 一定改动了 $z$ ，那么请输出 $-1$ 。

注： $gcd(x,y)$ 表示 $x$ 和 $y$ 的最大公约数，也就是最大的正整数 $d$ ，满足 $d$ 既是 $x$ 的约数，又是 $y$ 的

约数。

输入

第一行一个整数 $t$ ，表示有 $t$ 对正整数 $x$ 和 $z$ 。

接下来 $t$ 行，每行两个正整数 $x$ 和 $z$ ，含义见题目描述。

输出

对于每对数字输出一行，如果不存在满足条件的正整数 $y$ ，请输出 $-1$ ，否则输出满足条件的最小正整数 $y$ 。

样例

1
10 240

12

3 
5 30
4 8
11 11

6 
-1
1

说明

样例 1 解释

$x × y × gcd(x,y) = 10 × 12 × gcd(10,12) = 240$

数据范围

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

对于 $40\%$ 的数据， $t≤10$^$3$， $x≤10$^$6$， $z≤10$^$9$。

对于另 $30\%$ 的数据， $t≤10$^$4$ 。

对于另 $20\%$ 的数据， $x≤10$^$6$ 。

对于 $100\%$ 的数据， $1≤t≤5×10$^$5$， $1≤x≤10$^$9$， $1≤z＜2$^$63$ 。

来源

NOI Online 能力测试 2022 T2