La cursul de programare, Vlad fiind puţin cam plictisit a început să completeze o foaie cu cifre. Urmărindu-l cu atenţie, Georgiana observă că Vlad porneşte de la o matrice M1 de dimensiune L x L şi completează o matrice M2 de dimensiune 2L x 2L astfel:
Matricea M2 este împărţită în 4 cadrane de dimensiune LxL numerotate ca în figura alăturată.
În cadranul 1 se copiază matricea M1.
Cadranul 2 se completează cu matricea M1 rotită cu 90 de grade spre dreapta
Cadranul 3 se completează cu matricea M1 rotită cu 90 de grade spre stânga
Cadranul 4 se completează cu matricea M1 rotită cu 180 de grade
Pentru a-i pune la încercare gândirea info-oltenească, Georgiana îi propune lui Vlad următoarea provocare:
El va trebui să pornească de la matricea
După care va completa o matrice de dimensiuni 4x4 după modelul descris anterior obţinând matricea:
Apoi, din matricea completată anterior va obţine o altă matrice de dimensiuni 8x8:
Vlad va trebui să repete procedeul până când va reuşi să îi raspundă Georgianei la T întrebări de forma “Ce cifră se află în matrice pe linia x şi coloana y?”.
Cerinţă
Scrieţi un program care să furnizeze răspunsul la fiecare dintre cele T întrebări.
Date de intrare
Fişierul de intrare m4.in conţine pe prima linie numărul de întrebări T. Pe următoarele T linii se află cele T întrebări, câte o întrebare pe o linie. Pe cea de a i-a linie dintre cele T se află două numere naturale x y, separate prin spaţiu, reprezentând linia şi coloana pe care se află cifra căutată în cea de a i-a întrebare.
Date de ieşire
Fişierul de ieşire m4.out va conţine T linii. Pe linia i se va scrie cifra care conţine răspunsul la cea de a i-a întrebare din fişierul de intrare.
Restricţii
1 ≤ T ≤ 100
0 ≤ x, y ≤ 10100
Numerotarea liniilor şi a coloanelor începe de la 0
Pentru 30% din teste 0 ≤ x, y < 3500. Pentru 50% din teste 0 ≤ x, y ≤ 1018
