#include <stdio.h>
#include <stdlib.h>

int fn(int n)
{
    int x=1;  
    int y=1;  
    int tmp;  
    for(int i=2;i<n;i++)
    {  
        tmp=x;  
        x=y;  
        y=y+tmp;  
    }  
    return y; 
}
int main()
{
    int t,n,p;
    freopen("eins.in","r",stdin);
    freopen("eins.out","w",stdout);
    scanf("%d",&t);
    for(int i=0;i<t;i++)
    {
        scanf("%d %d",&n,&p);
        printf("%d\n",fn(n)%p);        
    }
    return 0;    
}