When little H was a primary school student, he loved to study. One day, in math class, the teacher gave the students a problem to think about: given an integer, it is known that its greatest common divisor with integer $a$ is $b$, and its greatest common divisor with integer $c$ is $d$. Please calculate the value of this integer.

Little H, who loved to study, soon discovered that there might be many integers satisfying these conditions, so he went to tell his teacher about his confusion. The teacher was very happy and encouraged little H to find all integers that are no less than $l$ and no greater than $r$ that satisfy these conditions, and to observe if there were any patterns. However, this problem was too difficult, and little H could not solve it at the time.

Now, little H, who is already in university, has rediscovered this problem while flipping through his primary school diary, but he still does not know how to solve it. Please help him solve this problem. Since there may be many such integers, you only need to output their sum.

Input

The first line contains an integer $T$, representing the number of test cases.

Each of the next $T$ lines contains six positive integers separated by spaces: $l$, $r$, $a$, $b$, $c$, and $d$.

Output

Output $T$ lines, each containing an integer, which is the answer for each test case—that is, the sum of all integers between $l$ and $r$ whose greatest common divisor with $a$ is $b$ and whose greatest common divisor with $c$ is $d$. If no such integer exists, output 0.

Examples

Input 1

3
1 20 2 2 12 6
4 6 3 3 4 4
1 1000000000 1 1 3 1

Output 1

24
0
333333333666666667

Note 1

For the first test case: The only numbers between 1 and 20 that satisfy the conditions are 6 and 18, and their sum is 24.

For the second test case: There are no numbers between 4 and 6 that satisfy the conditions.

Subtasks

For $10\%$ of the data, $1 \le l \le r \le 10^6$.

For $100\%$ of the data, $1 \le l \le r \le 10^{30}$, $1 \le a, b, c, d \le 10^{14}$, $1 \le T \le 4$. It is guaranteed that $b$ is a divisor of $a$ and $d$ is a divisor of $c$.