大蘑菇王降临到矮人身边,但并不是所有人都能见到他。只有少数被选中的人才能见到国王。
我们知道只有 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。