暂无测试数据。

题目描述

Kri 喜欢玩数字游戏。

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

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

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

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

输入格式

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

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

输出格式

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

数据范围

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

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

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

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

对于 $100\%$ 的数据，$1\leq t \leq 5 \times 10^5,1\leq x \leq 10^9,1\leq z < 2^{63}$。

1
10 240

12

3
5 30
4 8
11 11

6
-1
1