Extended Euclidean Algorithm 3

Problem Description

You are given $T$ test cases. Each case provides $a, b, d, l_1, r_1, l_2, r_2$; output how many integer solutions $(x, y)$ of $a x + b y = d$ satisfy $l_1 \leq x \leq r_1$ and $l_2 \leq y \leq r_2$.

Input Format

The first line contains an integer $T$.

The following $T$ lines each contain seven numbers: $a, b, d, l_1, r_1, l_2, r_2$.

Output Format

Output $T$ lines, each containing one number: the answer for that case.

Sample Input

3
1 2 5 0 10 0 10
100 150 1000 -10 0 0 10
3 2 1 0 100 0 100

Sample Output

3
2
0

Constraints

For $100\%$ of the data: $1 \leq T \leq 10^4$, $1 \leq a, b \leq 10^9$, $1 \leq d \leq 10^{18}$, $-10^{18} \leq l_1 \leq r_1 \leq 10^{18}$, $-10^{18} \leq l_2 \leq r_2 \leq 10^{18}$.