Fattoriali noiosi

Input

Nella prima riga è contenuto il numero di query $t (1 \leq t \leq 1000)$ t~(1 \le t \le 1000).

In ciascuna delle successive $t$ righe sono contenuti due numeri interi $n (1 \leq n \leq 2 \cdot 1 0^{9})$ n~(1 \le n \le 2 \cdot 10^9) e $p (1 < p \leq 2 \cdot 1 0^{9})$ p~(1 < p \le 2 \cdot 10^9), dove $p$ — è un numero primo. È noto che $∣ n - p ∣ \leq 1000$ |n - p| \le 1000.

Output

Per ogni query stampate il valore di $n! mod p$ n! \bmod p su una riga separata.

Esempi

Esempio 1

Loading