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