题目描述

一个正整数必是满足条件的当且仅当其是$a$的倍数或者$b$的倍数，求在$[l,r]$之间的共有多少满足条件的整数?

有多组询问，你需要对每组询问进行回答。

输入描述

第一行一个整数$T(1\le T\le 1000)$表示数据组数。

接下来$T$行，每行四个整数$a,b,l,r(1\le a,b\le 10^3,1\le l,r\le 10^3)$。

输出描述

输出$T$行，第$i$行表示第$i$组询问的答案

样例

输入

2
2 3 1 6
1 2 1 1

输出

4
1