题目内容

给定两个正整数底数 $u,v$，以及闭区间端点 $L,R$。

称整数 $t$ 可表，当且仅当存在整数系数 $\alpha,\beta$（可为负或 $0$），使得

$t=\alpha\cdot u+\beta\cdot v$。

请统计闭区间 $[L,R]$ 内有多少个整数是可表的。

输入描述

第一行一个整数 $g$（$1\le g\le 10^5$），表示询问组数。

接下来 $g$ 行，每行两个整数 $u,v$（$1\le u,v\le 10^9$）。

再接下来 $g$ 行，每行两个整数 $L,R$（$-10^{18}\le L\le R\le 10^{18}$）。

其中第 $i$ 组询问使用第 $i$ 行的 $u,v$ 与第 $i$ 行的 $L,R$。

输出描述

输出一行，包含 $g$ 个整数，相邻整数之间用单个空格隔开。

第 $i$ 个数表示第 $i$ 组询问中，区间 $[L,R]$ 内可表整数的个数。

样例1

输入

3
3 5
6 9
10 15
-3 7
1 20
100 100

输出

11 6 1

说明

第一组：底数 $3,5$，区间 $[-3,7]$ 内全部 $11$ 个数均可表。

第二组：底数 $6,9$，区间 $[1,20]$ 内可表的是 $3,6,9,12,15,18$，共 $6$ 个。

第三组：底数 $10,15$，区间仅含 $100$，且 $100$ 可表，答案为 $1$。