#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <iostream>

#include <cmath>

#define r register

using namespace std;

typedef long long LL;

inline LL read()

{

  r LL sum=;

  r char ch=getchar();

  while(ch<''||ch>'')ch=getchar();

  while(ch>=''&&ch<='')

  {

    sum=(sum<<)+(sum<<)+ch-'';

    ch=getchar();

  }

  return sum;

}

LL prime[];

bool isnot[];

LL T;

LL temp_a[][],a[][],b[],temp_b[];

LL m,p;

inline void Init()

{

  for(r LL i=;i<=(<<);i++)

  {

    if(!isnot[i])

      prime[++T]=i;

    for(r LL j=;j<=T&&prime[j]*i<=(<<);j++)

    {

      isnot[prime[j]*i]=;

      if(i%prime[j]==)break;

    }

  }

  m=read(),p=read();

}

inline LL Opha(LL x)

{

  r LL to=(LL)sqrt(x+0.5);

  r LL ans=x;

  for(r LL i=;prime[i]<=to;i++)

  if(x%prime[i]==)

  {

    ans=ans/prime[i]*(prime[i]-);

    while(x%prime[i]==)x/=prime[i];

  }

  if(x!=)

    ans=ans/x*(x-);

  return ans;

}

inline void Multi_One(LL k)

{

  memset(temp_b,,sizeof(temp_b));

  for(int i=;i<=;i++)

    for(int j=;j<=;j++)

      temp_b[i]=(temp_b[i]+a[i][j]*b[j]%k)%k;

  memcpy(b,temp_b,sizeof(b));

}

inline void Multi_Two(LL K)

{

  memset(temp_a,,sizeof(temp_a));

  for(int i=;i<=;i++)

    for(int j=;j<=;j++)

      for(int k=;k<=;k++)

        temp_a[i][j]=(temp_a[i][j]+a[i][k]*a[k][j]%K)%K;

  memcpy(a,temp_a,sizeof(a));

}

inline LL POW(LL x,LL k)

{

  a[][]=%k,a[][]=%k,a[][]=%k,a[][]=;

  b[]=%k,b[]=;

  while(x)

  {

    if(x&)Multi_One(k);

    x>>=,Multi_Two(k);

  }

  b[]%=k;

  return b[];

}

inline LL Pow(LL x,LL y,LL k)

{

  LL ans=%k;

  while(y)

  {

    if(y&)ans=ans*x%k;

    y>>=,x=x*x%k;

  }

  ans%=k;

  return ans;

}

inline void Work()

{

  while(m--)

  {

    r LL n=read(),q=read();

    r LL x=Opha(q);

    r LL y=POW(n-,x);

    printf("%lld\n",Pow(p,y,q));

  }

}

int main()

{

  Init();

  Work();

  return ;

}