CF185D.Visit of the Great

The Great Mushroom King descended to the dwarves, but not everyone managed to see him. Only the few chosen ones could see the King.

We know that only LCM(k_2_l + 1, k_2_l + 1 + 1, ..., k_2_r + 1) dwarves can see the Great Mushroom King. Numbers k, l, r are chosen by the Great Mushroom King himself in some complicated manner which is unclear to common dwarves.

The dwarven historians decided to document all visits of the Great Mushroom King. For each visit the dwarven historians know three integers k__i, l__i, r__i, chosen by the Great Mushroom King for this visit. They also know a prime number p__i. Help them to count the remainder of dividing the number of dwarves who can see the King, by number p__i, for each visit.

伟大的蘑菇王降临到矮人族，但并非所有人都能见到他。只有少数被选中的矮人才能目睹蘑菇王的真容。

我们已知，恰好有 $\mathrm{LCM}(k^{2^l}+1,\,k^{2^l+1}+1,\,\dots,\,k^{2^r}+1)$ 位矮人能够见到伟大的蘑菇王。其中数字 $k$、$l$、$r$ 由伟大的蘑菇王以某种复杂的方式选定，而普通矮人对此一无所知。

矮人历史学家决定记录下蘑菇王的每一次到访。对于每次到访，历史学家都知晓三个整数 $k_i$、$l_i$、$r_i$（即该次到访中蘑菇王所选定的数值），同时还知道一个质数 $p_i$。请帮助他们计算：每次到访时，能够见到蘑菇王的矮人数目对 $p_i$ 取模所得的余数。

The first line contains the single integer t (1 ≤ t ≤ 105) — the number of the King's visits.

Each of the following t input lines contains four space-separated integers k__i, l__i, r__i and p__i (1 ≤ k__i ≤ 106; 0 ≤ l__i ≤ r__i ≤ 1018; 2 ≤ p__i ≤ 109) — the numbers, chosen by the Great Mushroom King and the prime module, correspondingly.

It is guaranteed that for all visits number p__i is prime.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

第一行包含一个整数 $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 说明符。

For each visit print the answer on a single line — the remainder of dividing the number of the dwarves who can see the King this time, by number p__i. Print the answers for the visits in the order, in which the visits are described in the input.

对于每次访问，在一行中输出答案——即本次能够看见国王的矮人数量除以 $p_i$ 后所得的余数。请按照输入中描述访问顺序的顺序输出各次访问对应的答案。

We consider that LCM(_a_1, _a_2, ..., a__n) represents the least common multiple of numbers _a_1, _a_2, ..., a__n.

We consider that _x_0 = 1, for any x.

我们定义 $\mathrm{LCM}(a_1,\,a_2,\,\dots,\,a_n)$ 表示数 $a_1,\,a_2,\,\dots,\,a_n$ 的最小公倍数。

我们定义：对任意 $x$，有 $x^0 = 1$。