在这个问题中，你需要求出 $a$ 和 $b$ 的加法类中有多少个元素属于区间 $[l, r]$。

正整数 $a$ 和 $b$ 的加法类是指可以表示为若干个 $a$ 或 $b$ 之和的数的集合。形式化地，该集合定义为：$\{x \cdot a + y \cdot b \mid x, y \in \mathbb{Z}, x, y \ge 0\}$。

给定 $a, b$ 以及两个整数 $l$ 和 $r$ ($l \le r$)，求加法类中有多少个元素 $e$ 满足不等式 $l \le e \le r$。

输入格式

输入包含一个或多个测试用例。输入的第一行包含一个整数 $t$，表示测试用例的数量 ($1 \le t \le 10\,000$)。接下来是各个测试用例。

每个测试用例由两行组成。第一行包含两个正整数 $a$ 和 $b$ ($1 \le a, b \le 10^9$)。第二行包含两个整数 $l$ 和 $r$ ($0 \le l \le r \le 10^{18}$)。

输出格式

对于每个测试用例，在单独的一行中输出答案。答案为一个整数：加法类中属于 $[l, r]$ 的元素个数。

样例

输入 1

2
3 5
6 8
6 4
13 13

输出 1

2
0

说明

该样例包含两个测试用例。

在第一个测试用例中，$a = 3$ 且 $b = 5$。这些数的加法类包含数字 $0, 3, 5, 6 = 3 + 3, 8 = 3 + 5, 9 = 3 + 3 + 3, \dots$。其中有两个数属于区间 $[6, 8]$。

在第二个测试用例中，$a = 6$ 且 $b = 4$。显然，它们的加法类只包含偶数，因此没有元素属于区间 $[13, 13]$。