Цвет

Бусинки n цветов соединены между собой в циклическое ожерелье из n бусинок (n ≤ 10^9). Вам следует подсчитать количество различных ожерелий, которое можно получить. В ожерелье не обязательно использовать все n цветов. Повторениями, полученными в результате вращения ожерелья вокруг центра, следует пренебречь.

Вывести ответ по модулю p.

Входные данные

Первая строка содержит количество тестов x (x ≤ 3500). Каждая из следующих x строк содержит два числа n и p (1 ≤ n ≤ 10^9, 1 ≤ p ≤ 30000).

Выходные данные

Для каждого теста вывести ответ в отдельной строке.

Примеры