Нудні факторіали

Вхідні дані

У першому рядку міститься кількість запитів $t (1 \leq t \leq 1000)$ t~(1 \le t \le 1000).

У кожному з наступних $t$ рядків містяться два цілих числа $n (1 \leq n \leq 2 \cdot 1 0^{9})$ n~(1 \le n \le 2 \cdot 10^9) та $p (1 < p \leq 2 \cdot 1 0^{9})$ p~(1 < p \le 2 \cdot 10^9), де $p$ — просте число. Відомо, що $∣ n - p ∣ \leq 1000$ |n - p| \le 1000.

Вихідні дані

Для кожного запиту виведіть значення $n! mod p$ n! \bmod p в окремому рядку.

Приклади

Приклад 1

Loading