Колір

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

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

Вхідні дані

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

Вихідні дані

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

Приклади