D. Пришествие
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

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

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

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

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

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

В каждой из следующих t строк входных данных записано четыре целых числа, разделённых пробелами, ki, li, ri и pi (1 ≤ ki ≤ 106; 0 ≤ li ≤ ri ≤ 1018; 2 ≤ pi ≤ 109) — числа, которые выбрал Великий Грибной король, и простой модуль, соответственно.

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

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

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

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

Примеры
Входные данные
2
3 1 10 2
5 0 4 3
Выходные данные
0
0
Примечание

Считается, что LCM(a1, a2, ..., an) обозначает наименьшее общее кратное чисел a1, a2, ..., an.

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