Fie $A$ o matrice binară cu $N$ linii şi $M$ coloane. Se numeşte drum "dreapta-jos" orice succesiune de celule $(x0, y0), (x1, y1) ... (x(k - 1), y(k - 1))$ cu proprietatea că oricare ar fi $1 ≤ i ≤ k - 1$, $x(i) = x(i - 1) + 1 şi y(i) = y(i - 1) sau x(i) = x(i - 1) si y(i) = y(i - 1) + 1$. Câte drumuri "dreapta-jos" există care încep în colţul din stânga sus, se termină în colţul dreapta jos şi conţin doar celule de tip $1$?

*Glumim.* Această problemă este mult prea cunoscută. Atât de cunoscută încât, de-a lungul istoriei, Comisiile au dezvoltat o precizie remarcabilă în alcătuirea testelor de acest tip. Mai exact, dându-se un număr natural $C$ Comisia poate să producă o matrice de dimensiuni rezonabile pentru care răspunsul la întrebarea de mai sus este exact $C$. Spoiler alert, asta trebuie să faceţi şi voi!

*Glumim.* Această problemă este mult prea cunoscută. Atât de cunoscută încât de-a lungul istoriei Comisiile au dezvoltat o precizie remarcabilă în alcătuirea testelor de acest tip. Mai exact, dându-se un număr natural $C$, Comisia poate să producă o matrice de dimensiuni rezonabile pentru care răspunsul la întrebarea de mai sus este exact $C$. Spoiler alert, asta trebuie să faceţi şi voi!

h2. Date de intrare

h2. Restricţii

* Aria maxima a unei matrici (N x M) pe care o afisati trebuie să fie $1600$.

* Numărul de celule $(N x M)$ al fiecarei matrice pe care o afisati trebuie să fie maxim $1600$.

* $1 ≤ T ≤ 500$
* $1 ≤ C{~i~} ≤ 66.666.666$
* Pentru teste in valoare de $10$ puncte, $C{~i~} ≤ 800$