#include<iostream> #include<cstdio> using namespace std; inline int read(){ static int 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; } int main(){ //freopen("number.in" , "r" , stdin); //freopen("number.out" , "w" , stdout); int t ; cin >> t ; while(t--){ int n , p ; n = read(); p = read(); for(int l = 1 ; ; l++) if( ((2*l*n + n*n - n) / 2) % p == 0){ printf("%d\n", l) ; break; } else if( ((2*l*n + n*n - n) / 2) > p){ printf("-1\n") ; break; } } return 0; }