题目内容

给定四个正整数 $x$, $y$, $l$, $r$，求在闭区间 [$l$, $r$] 内，有多少个整数 $n$ 满足：存在整数 $a$, $b$，使得 $a$ * $x$ + $b$ * $y$ = $n$。

输入描述

第一行输入一个整数 $t$，表示查询的组数。 接下来 $t$ 行，每行输入四个整数 $x$, $y$, $l$, $r$，含义如题目描述。

输出描述

对每组查询输出一行，表示闭区间 [$l$, $r$] 内满足条件的整数 $n$ 的个数。

样例1

输入

3
2 4 1 10
3 5 1 10
6 10 7 20

输出

5
10
7

说明

第一组查询 $x$ = $2$, $y$ = $4$，能被表示出来的数恰好是 $2$ 的倍数，区间 [$1$, $10$] 内有 $2$, $4$, $6$, $8$, $10$ 共 $5$ 个。 第二组查询 $x$ = $3$, $y$ = $5$，例如 $3$ * $2$ + $5$ * ($-1$) = $1$，可以表示出所有整数，区间 [$1$, $10$] 内的 $10$ 个数全部满足。 第三组查询 $x$ = $6$, $y$ = $10$，能被表示出来的数恰好是 $2$ 的倍数，区间 [$7$, $20$] 内有 $8$, $10$, $12$, $14$, $16$, $18$, $20$ 共 $7$ 个。

样例2

输入

2
1000000000000000000 1000000000000000000 1 1000000000000000000
7 7 1 6

输出

1
0

说明

第一组查询 $x$ = $y$ = $1000000000000000000$，能被表示出来的数是 $1000000000000000000$ 的倍数，区间 [$1$, $1000000000000000000$] 内只有 $1000000000000000000$ 这一个。 第二组查询 $x$ = $y$ = $7$，能被表示出来的数是 $7$ 的倍数，区间 [$1$, $6$] 内一个都没有，输出 $0$。