#include <bits/stdc++.h> using namespace std; #define ll long long inline ll read ( ) { static ll x=0, c=getchar(); for ( ; c <=47|| c >=58; c=getchar() ) ; for ( x=0; c>=48&&c <=57; c=getchar()) x=(x<<3)+(x<<1)+(c &15); return x ; } ll n, q, t; ll gcd(ll x, ll y) { while (y) { ll temp = x; x = y; y = temp % y; } return x; } int main() { //freopen("number2.in", "r", stdin); //freopen("number.out", "w", stdout); // scanf("%lld", &t); t = read(); while(t--) { // scanf("%lld%lld", &n, &q); n = read(), q = read(); if (gcd(n, q) != 1 && (((1 - n) % q + q) % q)) { puts("-1"); } else { if ((1 - n) & 1 && !(q & 1)) { puts("-1"); } else { long long l; if ((1 - n) & 1) { l = ((1 - n + q) / 2 % q + q) % q; if (l == 0) { l += q; } } else { l = ((1 - n) / 2 % q + q) % q; } printf("%lld\n", l); } } } }