//思路：浮点数转二进制，a/b的结果为 gcd（a，b）*最简分式（n/m）的结果
//苹果能分的前提是人数得是一个2的次幂数，通过切割只能分为形同0.001的二进制小数
//a/b的二进制如果在从左到右的sp位为 1 ，则需要切割到这个情况
//一个苹果切割到这一位共用 2^(sp-1)-1 刀 ， 得到 2^(sp) 份这样的苹果
//则要加上 (m /(1 << sp)) * ((1 << sp) - 1) 刀
//结果乘上先前优化的gcd
#define int long long
#define ld long double
using namespace std;
int gcd(int a, int b)
{
if (b)return gcd(b, a % b);
else return a;
}
void op()
{
int n, m;
cin >> n >> m;
if (n % m == 0)cout << 0 << endl;
else
{
int tmp = m;
int k = gcd(n, m);
n /= k;
m /= k;
if (m % 2)
{
cout << -1 << endl;;
return;
}
int fg = 0;
int kk = m;
while (kk)
{
if (kk & 1)fg++;
kk >>= 1;
if (fg > 1)
{
cout << -1 << endl;
return;
}
}
bool st = true;
int sp = 1,ans=0;
while (st&&sp<=33)
{
if (((n << sp)/m) & 1)
{
ans += (m / ((int)1 << sp)) * (((int)1 << sp) - 1);
}
if ((n << sp) % m == 0)
{
st = false;
}
sp++;
}
cout << ans * k << endl;
}
}
signed main()
{
int t;
cin >> t;
while (t--)op();
return 0;
}