Dreamoon очень любит последовательности. Поэтому он придумал задачу про последовательность, которую нельзя найти на OEIS:
Вам дано два целых числа \(d, m\), вам нужно найти количество массивов \(a\), удовлетворяющих следующим ограничениям:
Так как количество возможных массивов может быть слишком большим, вам нужно найти его по модулю \(m\).
В первой строке записано целое число \(t\) (\(1 \leq t \leq 100\)) обозначающее количество наборов входных данных в задаче.
Каждая из следующих \(t\) строк содержит два целых числа \(d, m\) (\(1 \leq d, m \leq 10^9\)).
Обратите внимание, что \(m\) необязательно простое!
Для каждого набора входных данных, выведите количество массивов \(a\), удовлетворяющих всем ограничениям, по модулю \(m\).
10 1 1000000000 2 999999999 3 99999998 4 9999997 5 999996 6 99995 7 9994 8 993 9 92 10 1
1 3 5 11 17 23 29 59 89 0
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач