Los numeros Fibonacci son: (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...) y se define con la siguiente recurrencia:

$f_n=f_{n-1}+f_{n-2}$

Escriba un programa que calcule $F(n) \mod m$.

La entrada consiste de varios casos de prueba. La primera linea contiene el número de casos de prueba. Cada caso de prueba viene en una una linea y contiene dos números ($0 \leq n \leq 90$), ($2 \leq m \leq 10000$).

Por cada caso de prueba imprime $F(n) \mod m$.