CF185D Visit of the Great

伟大的蘑菇王降临矮人族，但并不是每个人都能见到他。只有少数被选中的矮人能够看到蘑菇王。 我们已知，只有 $LCM(k^{2^l}+1, k^{2^{l+1}}+1, \ldots, k^{2^r}+1)$ 名矮人能见到伟大的蘑菇王。这里的数字 $k$、$l$、$r$ 是由伟大的蘑菇王以某种复杂的方式自己选出的，普通的矮人无法理解。 矮人历史学家决定记录下蘑菇王所有的到访。对于每一次到访，他们都知道由蘑菇王选定的三个整数 $k_i$、$l_i$、$r_i$，以及一个质数 $p_i$。请你帮他们计算，每次能见到蘑菇王的矮人数对 $p_i$ 取余的结果。

第一行包含一个整数 $t$ $(1 \leq t \leq 10^5)$ —— 蘑菇王到访的次数。 接下来的 $t$ 行，每行包含四个用空格分隔的整数 $k_i$、$l_i$、$r_i$ 和 $p_i$ $(1 \leq k_i \leq 10^6;\ 0 \leq l_i \leq r_i \leq 10^{18};\ 2 \leq p_i \leq 10^9)$ —— 依次为蘑菇王选定的数字和取余的质数。 保证所有到访中 $p_i$ 均为质数。 请不要在 C++ 中使用 %lld 来读写 64 位整数。建议使用 cin、cout 流或 %I64d 方式。

对于每次到访，输出一行结果，表示该次能见到蘑菇王的矮人数对 $p_i$ 取余的值。按照输入顺序依次输出结果。

记 $LCM(a_1, a_2, \ldots, a_n)$ 为 $a_1, a_2, ..., a_n$ 的最小公倍数。 我们认为 $x^0 = 1$，对于任意 $x$ 均成立。 由 ChatGPT 5 翻译