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