var
  t,w,i:longint;
  q,p,x,y,ans:int64;
begin
  readln(t);
  for w:=1 to t do
  begin
    readln(q,p);
    q:=abs(q);
    if q mod 2=0 then
    begin
      x:=q-1;y:=(q-2) div 2;
    end else
    begin
      x:=q-2;y:=(q-1) div 2;
    end;
    ans:=0;
    while x>0 do
    begin
      if x mod 2=1 then ans:=(ans+y) mod p;
      y:=y*2 mod p;
      x:=x div 2;
    end;
    writeln(ans);
  end;
end.