#include
#include
#include
#include
using namespace std;
typedef long long llg;
llg func(llg x,llg y,llg m)
{
llg ans = 0;
llg ret = x;
while(y)
{
if(y&1) ans = (ret + ans) % m;
y >>= 1LL;
ret = (ret + ret) % m;
}
return ans;
}
int main()
{
int cas;
llg p,q;
scanf("%d",&cas);
while(cas--)
{
scanf("%I64d%I64d",&p,&q);
if(p == 2)
{
p = p % q;
printf("0\n");
continue;
}
p -= 2LL;
llg t,f;
if(p&1)
{
t = (p+1)/2;
f = p;
} else
{
t = p / 2;
f = p+1;
}
//cout<