Задачі
Колір
Колір
Намистинки n кольорів з'єднані між собою у циклічне намисто з n намистинок (n ≤ 10^9). Вам потрібно підрахувати кількість різних намист, які можна отримати. У намисті не обов'язково використовувати усі n кольорів. Повтореннями, отриманими у результаті обертання намиста навколо центру, потрібно знехтувати.
Відповідь виведіть по модулю p.
Вхідні дані
Перший рядок містить кількість тестів x (x ≤ 3500). Кожен з наступних x рядків містить два числа n та p (1 ≤ n ≤ 10^9, 1 ≤ p ≤ 30000).
Вихідні дані
Для кожного тесту вивести відповідь в окремому рядку.
Приклад
Вхідні дані #1
5 1 30000 2 30000 3 30000 4 30000 5 30000
Вихідні дані #1
1 3 11 70 629