Program cog1426;
    Var
        T,N,P,I,J:Longint;
        A,S,R:Array[1..4]Of Int64;
    Begin
        Assign(Input,'eins.in');
        Assign(Output,'eins.out');
        Reset(Input);
        Rewrite(Output);
        Readln(T);
        Repeat
            S[1]:=1;
            S[2]:=1;
            S[3]:=1;
            S[4]:=0;
            A[1]:=1;
            A[2]:=0;
            A[3]:=0;
            A[4]:=1;
            Readln(N,P);
            While N>0 Do
                Begin
                    If N And 1=1 Then
                        Begin
                            R[1]:=(S[1]*A[1]+S[2]*A[3]) Mod P;
                            R[2]:=(S[1]*A[2]+S[2]*A[4]) Mod P;
                            R[3]:=(S[3]*A[1]+S[4]*A[3]) Mod P;
                            R[4]:=(S[3]*A[2]+S[4]*A[4]) Mod P;
                            Move(R[1],A[1],32);
                        End;
                    R[1]:=(S[1]*S[1]+S[2]*S[3]) Mod P;
                    R[2]:=(S[1]*S[2]+S[2]*S[4]) Mod P;
                    R[3]:=(S[3]*S[1]+S[4]*S[3]) Mod P;
                    R[4]:=(S[3]*S[2]+S[4]*S[4]) Mod P;
                    Move(R[1],S[1],32);
                    N:=N Shr 1;
                End;
            Writeln(A[3]);
            Dec(T);
        Until T=0;
        Close(Input);
        Close(Output);
    End.