等值分数矩形计数

题目描述

每次询问给定正整数 a、b、X、Y，统计正整数对 (c,d)，使 c≤X、d≤Y 且 c/d=a/b。

输入格式

第一行输入 Q，满足 1≤Q≤2×10^5。接下来 Q 行输入 a、b、X、Y，均满足 1≤数值≤10^18。

输出格式

按询问顺序输出 Q 行，每行输出符合条件的二元组数量。

样例

输入

1
2 3 20 30

输出

10