eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Колір

Колір

Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB

Намистинки n кольорів з'єднані між собою у циклічне намисто з n намистинок (n10^9). Вам потрібно підрахувати кількість різних намист, які можна отримати. У намисті не обов'язково використовувати усі n кольорів. Повтореннями, отриманими у результаті обертання намиста навколо центру, потрібно знехтувати.

Відповідь виведіть по модулю p.

Вхідні дані

Перший рядок містить кількість тестів x (x 3500). Кожен з наступних x рядків містить два числа n та p (1n 10^9, 1 p 30000).

Вихідні дані

Для кожного тесту вивести відповідь в окремому рядку.

Приклад

Вхідні дані #1
5
1 30000
2 30000
3 30000
4 30000
5 30000
Вихідні дані #1
1
3
11
70
629
Автор Lou Tiancheng
Джерело POJ Monthly