Peak

Cerință

Se dă un întreg $Q$ și apoi $Q$ interogări de tipul $(a, b, c, d, s, t)$ numere întregi. Se cere numărul de perechi $(x, y)$ de întregi care să respecte simultan condițiile:

• $\frac{a}{b} \leq \frac{x}{y} \leq \frac{c}{d}$
• $s \leq y \leq t$

Date de intrare

Pe prima linie se găsește un întreg $Q$. Pe fiecare din următoarele $Q$ linii se află câte $6$ întregi $a$, $b$, $c$, $d$, $s$, și $t$, reprezentând interogările.

Date de ieșire

Pe linia $i$ se va afișa răspunsul la cea de-a $i$-a interogare.

Restricții și precizări

• $1 \leq Q \leq 10^5$;
• $1 \leq a, b, c, d \leq 100$;
• $1 \leq s, t \leq 10^7$;
• Se garantează că $s \leq t$ și $\frac{a}{b} \leq \frac{c}{d}$ pentru oricare interogare;
• Pentru teste în valoare de $19$ puncte, $t - s \leq 10^3$;
• Pentru alte teste în valoare de $45$ de puncte, $s$ și $t$ sunt divizibile cu cel mai mic multiplu comun al lui $b$ și $d$;
• Pentru alte teste în valoare de $36$ de puncte, nu există restricții suplimentare.

Exemplu

stdin

2
1 5 2 3 1 3
3 10 7 2 8 9

stdout

3
55

Explicație

Pentru primul exemplu, perechile $(x, y)$ ce satisfac condiția din enunț sunt $(1, 2); (1, 3); (2, 3)$, pentru că $\frac{1}{5} \leq \frac{1}{2}, \frac{1}{3}, \frac{2}{3} \leq \frac{2}{3}$, iar $1 \leq y \leq 3$ pentru fiecare pereche.

Pentru al doilea exemplu, va trebui să ne credeți pe cuvânt.