← 返回题目列表

Codeforces · 185/D

D. 伟大的来访

中文机器翻译题面 查看原题

大蘑菇王降临到矮人身边,但并不是所有人都能见到他。只有少数被选中的人才能见到国王。

我们知道只有 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) — 由 Great Mushroom King 和 prime 模块相应选择的数字。

保证对于所有访问,数字 pi 都是素数。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

输出

每次访问都将答案打印在一行上 — 这次可以看到国王的矮人数量除以 pi 的余数。按顺序打印访问的答案,其中输入中描述了访问。

示例

输入 #1

2
3 1 10 2
5 0 4 3

输出 #1

0
0

注意

我们认为 LCM(a1, a2, ..., an) 表示数字 a1, a2, ..., an 的最小公倍数。

对于任何 x,我们认为 x0 = 1。