固定一个整数 $A$。考虑满足以下两个条件的序列 $\{f(n)\}$：

1. $f(0) = 0, f(1) = 1$；
2. 对于任何整数 $n > 1$，有 $f(n) = A \cdot f(n - 1) + f(n - 2)$。

给定一个素数 $p$ 和一个整数 $x$ ($0 \le x < p$)，你的任务是计算 $|\{n : L \le n \le R, f(n) \pmod p = x\}|$，即满足 $L \le n \le R$ 且 $f(n) \pmod p = x$ 的下标 $n$ 的个数。

输入格式

包含一个或多个测试用例。 输入的第一行包含一个整数 $T$，表示测试用例的数量 ($1 \le T \le 42$)。 接下来的 $T$ 行，每行包含五个整数 $A, p, x, L$ 和 $R$ ($0 \le A < 10^9, 2 < p < 10^9, 0 \le x < p, 1 \le L \le R \le 10^{18}$)。保证 $p$ 是素数。

输出格式

输出 $T$ 行，每行对应一个测试用例的答案。

样例

输入 1

2
1 5 0 1 5
2 29 12 3 6

输出 1

1
2