题目背景

小 z 最近学习了最大公约数。

题目描述

这是一道最大公约数的题，那么显然要有两个数 $a,b$。现在小 z 给你这样一个等式 $\dfrac{a^2}{b} = \gcd(a,b^2)$，小 z 告诉你 $a$ 和 $\gcd(a,b)$，他希望你告诉他最小的 $b$，如果不存在满足的 $b$ 输出 -1。

输入格式

第一行一个整数 $T$ 表示数据组数。

接下来 $T$ 行，每行两个整数表示 $a, \gcd(a,b)$。

输出格式

每组数据一行输出一个整数 $b$，若不存在输出-1。

2
1 1
6547265472 65472

1
-1

提示

对于 $30\%$ 的数据，满足 $1\leq a,\gcd(a,b) \leq 10^3$。

对于 $60\%$ 的数据，满足 $1\leq \cfrac{a}{\gcd(a,b)} \leq 10^6$。

对于额外 $10\%$ 的数据，满足 $\gcd(a,b) = 1$。

对于 $80\%$ 的数据，满足 $1\leq T \leq 5$，$1\leq a,\gcd(a,b) \leq 10^9$。

对于 $100\%$ 的数据，满足 $1\leq T \leq 10^5$，$1\leq a,\gcd(a,b) \leq 10^{18}$。