小T认为2019是一个优美的数字，更一般的，小T认为2019的倍数也是一个优美的数字。 现在问题来了，任意给出l1,r1,l2,r2四个数，小T想知道有多少数对(x,y)满足：
x∗y mod 2019=0
l1≤x≤r1
l2≤y≤r2
输入格式
输入包含多组数据，第一行一个整数T，表示数据组数。 之后T行，每行一组数据包含四个整数l1,r1,l2,r2。
输出格式
对于每组数据，输出一个整数表示所求的数对数量，每组输出以换行结尾。
样例
样例输入
3
1 3 1 2019
1 2019 1 2019
1 1000000000 1 1000000000
样例输出
5
6725
1649754749959584
数据范围与约定
对于30%的数据保证：|r1−l1|≤2000,|r2−l2|≤2000,T≤5;
另有30%的数据保证：l1=l2=1,T≤50;
对于100%的数据保证：1≤l1≤r1≤109,1≤l2≤r2≤109,T≤105