Олимпиадный тренинг

Задача . D. Пришествие

Задача

К гномикам спустился их Великий Грибной король, но не каждый мог увидеть его. Лишь только некоторое количество избранных гномиков могли увидеть короля.

Известно, что Великого Грибного короля могут увидеть лишь LCM(k^{2^l} + 1, k^{2^l + 1} + 1, ..., k^{2^r} + 1) гномиков. Числа k, l, r каким-то непонятным простым гномикам способом выбирает Великий Грибной король.

Гномики историки решили задокументировать все пришествия Великого Грибного короля. Для каждого пришествия, гномики историки знают три числа k_i, l_i, r_i, которые выбрал Великий Грибной король в это пришествие, и простое число p_i. Помогите им посчитать остаток от деления на p_i количества гномиков, которые могут увидеть короля, для каждого из пришествий.

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

В первой строке входных данных записано единственное целое число t (1 ≤ t ≤ 10⁵) — количество пришествий короля.

В каждой из следующих t строк входных данных записано четыре целых числа, разделённых пробелами, k_i, l_i, r_i и p_i (1 ≤ k_i ≤ 10⁶; 0 ≤ l_i ≤ r_i ≤ 10¹⁸; 2 ≤ p_i ≤ 10⁹) — числа, которые выбрал Великий Грибной король, и простой модуль, соответственно.

Гарантируется, что во всех пришествиях число p_i простое.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++, вместо него рекомендуется использовать потоки cin, cout, а также спецификатор %I64d.

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

Для каждого пришествия выведите ответ в отдельной строке — остаток от деления количества гномов, которые смогут увидеть короля, на число p_i. Ответы для пришествий выводите в том порядке, в котором заданы описания пришествий во входных данных.

Примечание

Считается, что LCM(a₁, a₂, ..., a_n) обозначает наименьшее общее кратное чисел a₁, a₂, ..., a_n.

Считается, что x⁰ = 1, для любых x.

Примеры

№	Входные данные	Выходные данные
1	2 3 1 10 2 5 0 4 3	0 0

time 3000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет