#include <bits/stdc++.h> using namespace std; inline int Read() { int x = 0; char ch = getchar(); for(;ch < '0' || ch > '9';ch = getchar()); for(;ch >= '0' && ch <= '9';ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48); return x; } int main() { int t = Read(); while(t--) { int n = Read(),p = Read(); if(p == 1) { puts("1"); continue; } int now = n * (n + 1) / 2,ans = 1; now %= p; while(now) { ans++; if(ans >= p) { puts("-1"); break; } now = (now + n) % p; } if(ans < p) printf("%d\n",ans); } return 0; }