7. Kocúre a klbko

Anička a Bláčik sú dve rozkošné mačiatka, a ako typické mačiatka, ich obľúbená hračka je špagát. Zvykli ho najmä naháňať, ale odkedy zaspali na knižke o teórii hier, osmózou¹ sa k nim dostali aj nejaké vedomosti, a ich hry začali byť elaborátnejšie.

Konkrétne, keď sa prebudili po výdatnom matematickom spánku, Bláčik a Anička si schmatli dva špagáty, jeden s dĺžkou \(a\) a druhý s dĺžkou \(b\) mačkometrov, a postupne sa striedajú na ťahu. Mačiatko si vyberie špagát a skráti ho o celočíselný pozitívny násobok dĺžky druhého špagátu². Samozrejme, mačiatko bez špagátu je smutné mačiatko, a preto ani jedno z nich nechce špagát ťahom úplne zmiznúť.

A keďže mačiatka sú naozaj hyperaktívne, raz ako sa naučili hrať hru, budú ju hrať viackrát. Menovite, klbko z ktorého špagáty berú vystačí na to, aby si vyskúšali hru zo všetkými možnými dĺžkami prvého špagátu v rozmedzí \(a_0 \leq a\leq a_1\), a druhého špagátu v rozmedzí \(b_0\leq b\leq b_1\).

Po niekoľkých ďalších šlofíkoch na knihe sa už Anička a Bláčik naučili hrať optimálne a zaujímalo by ich, koľko z týchto hier výhrá ktoré z nich. Na vylúštenie tejto záhady ešte dosť nespali³ – hrajú sa predsa so špagátmi! – tak im budete s touto otázkou musieť pomôcť vy!

Úloha

Anička a Bláčik sa hrajú nasledovnú hru. Majú dva špagáty, s dĺžkami \(a\) a \(b\) mačkometrov. Striedajú sa v ťahoch, mačiatko na ťahu si vždy vyberie celé číslo \(k \geq 1\), a buď skráti prvý špagát o \(k\cdot b\) mačkometrov, alebo druhý špagát o \(k\cdot a\) mačkometrov. Prehráva mačiatko, ktoré jeden zo špagátov úplne zmizne. Samozrejme, špagát nemožno skrátiť na negatívnu dĺžku.

Hru sa hrajú viackrát, konrkétne pre každú kombináciu \(a\) a \(b\) v rozsahu \(a_0\leq a\leq a_1\) a \(b_0\leq b\leq b_1\) vrátane (hrajú tak \((a_1 - a_0 + 1)(b_1 - b_0 + 1)\) hier).

Anička vždy začína. Koľko z hier vyhrá, ak obe mačiatka hrajú optimálne?

Formát vstupu

V jednom vstupe sa bude nachádzať viacero testovacích vstupov. Prvý riadok vstupu obsahuje celé číslo \(1\leq t\leq 10^5\) – počet testovacích vstupov.

Na ďalších \(t\) riadkoch sa na každom nachádzajú štyri celé čísla oddelené medzerou: \(a_0, a_1, b_0\) a \(b_1\). Je zaručené, že \(1\leq a_0, a_1,b_0,b_1\leq 10^9\), \(0\leq b_1 - b_0, a_1 - a_0 \leq 10^6\).

Úloha má štyri sady. V prvej sade platí, že \(a_0,a_1,b_0,b_1\leq 500\). V druhej sade platí, že \(a_0=a_1\) a \(b_0=b_1\). V tretej sade platí, že \(a_1-a_0, b_1-b_0\leq 10^5\).

Je garantované, že súčet \(a_1-a_0 + 1\) (resp \(b_1-b_0 + 1\)) v prvých troch sadách neprekročí \(10^5\), a v štvrtej sade neprekročí \(5\cdot 10^6\).

Formát výstupu

Pre každý z \(t\) vstupov vypíšte jeden riadok a v ňom jedno celé číslo: počet hier v ktorých Anička vyhrá, ak obe mačiatka hrajú optimálne.

Dávajte si pozor, že výstup môže byť pomerne veľký. Ak programujete v pythone, odporúčame vám vypisovať celý výstup naraz pomocou jediného použitia print. V prípade, ak používate C++, odporúčame vám používať \n namiesto endl.

Príklad

Input:

2
11 11 2 2
1 6 1 6

Output:

1
20

*V prvom prípade hrajú mačiatka jedinú hru: s \(a=11\) a \(b=2\). Anička v prvom ťahu skráti špagát dĺžky \(11\) na dĺžku \(3\) (druhý špagát ostáva dlhý dva mačkometre). Bláčik nemá na výber, skráti špagát dĺžky \(3\) o dva mačkometre, a Aničke zostanú špagáty s dĺžkami \(1\) a \(2\). Keď z dlhšieho odhryzne jeden mačkometer, Bláčikovi ostanú dva špagáty dĺžky jedna. Nemá na výber, akýmkoľvek ťahom prehráva.