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