romb

Noul împărat INFO al ţării ONI2013 a decis să împartă ţara în regiuni codificate după un algoritm stabilit prin decret. Ţara are formă de romb, având centrul în punctul de coordonate $(0,0)$ şi lungimile semi-diagonalelor $dx$ şi $dy$ (ca în figura $1$).

Împăratul alege un număr $k$, reprezentând numărul de etape de parcurs, astfel:

• în prima etapă, rombul iniţial este împărţit în patru regiuni egale, în formă de romb, fiecare latură fiind jumătate din latura rombului iniţial;
• în fiecare din celelalte $k - 1$ etape, orice romb rezultat la etapa precedentă este împărţit în alte patru romburi egale, aşa cum este descris în prima etapă.

Astfel, după $k$ etape vom avea în total $4^k$ regiuni egale, în formă de romb.

Codificarea regiunilor este făcută astfel:

• în prima etapă, rombul iniţial se împarte în patru regiuni, codificate în sens trigonometric cu valorile $1, 2, 3$ și $4$ (ca în figura $2$);
• în fiecare din celelalte etape, se reface codificarea, astfel: dacă rombul anterior avea la etapa precedentă codul $X$, cele patru romburi obţinute după divizarea curentă vor avea acum codurile $4 \cdot X - 3, 4 \cdot X - 2, 4 \cdot X - 1, 4 \cdot X$ (figura $3$).

Cerinţă

Împăratul doreşte să ştie după cele $k$ etape, care este codul regiunii unde se află un oraş dat prin coordonatele ($Cx$, $Cy$).

Date de intrare

Pe prima linie a fişierului romb.in se află numărul $T$ de întrebări (seturi de date de test). Pe fiecare din următoarele $T$ linii se află câte un set de date de test cu valorile $dx,dy,k,Cx,Cy$, cu semnificaţia anterioară, separate prin câte un spațiu.

Date de ieşire

Fişierul romb.out va conţine $T$ linii, pe fiecare linie $i$ fiind răspunsul la întrebarea $i$, un număr natural reprezentând codul regiunii în care se află oraşul de coordonate date (pentru testul $i$).

Restricţii şi precizări

• $-20 \ 000 \leq dx, dy, Cx, Cy \leq 20 \ 000$
• $0 < k < 20$
• $0 < T < 10$
• $dx$ și $dy$ sunt numere naturale iar $Cx$ și $Cy$ sunt numere întregi
• Se garantează că punctul de coordonate $(Cx,Cy)$ nu se află la distanţă mai mică de $10^{-7}$ faţă de latura unui romb obținut în ultima etapă.

Exemplu

romb.in

2
10 8 2 6 -2
12 16 3 -2 4

romb.out

15
10

Explicație

Numarul de teste este $T=2$.

Orașul de coordonate $(6,-2)$, se află în regiunea codificată cu $15$

Orașul de coordonate $(-2, 4)$, se află în regiunea codificată cu $10$