Majstorija

Svi znaju kako je Mars svjetski putnik. A samo svjetskim putnicima se dešavaju nezgode. Ovoga puta, iskusni posrednik se izgubio na otoku punom ljutih natjecatelja.

Kako bi bio vidljiv i kako bi ga Povjerenstvo spasilo s otoka svojim službenim helikopterom, on mora nacrtati u pijesku matricu dimenzija N \times M. U svako polje te matrice ucrtat će ili broj 0 ili broj 1.

Ipak, nije tako prosto. Kako bi se opravdalo trošenje goriva za helikopter, Marsova matrica mora zadovoljiti uvjete:

• u retku i (za i=1,2,\ldots,N), zbroj brojeva mora biti djeljiv s i
• u stupcu j (za j=1,2,\ldots,M), zbroj brojeva mora biti djeljiv s j
• svaki redak i svaki stupac moraju imati po barem jednu jedinicu u sebi.

Pomozite Marsu tako što ćete mu reći je li moguće nacrtati takvu matricu, i ako je moguće, dajte mu primjer jedne bilo koje takve matrice. Inače, morat će čitati žalbe ljutih natjecatelja.

Opis ulaza

U prvoj liniji standardnog ulaza dan je jedan prirodni broj T - broj test primjera.

U narednih T linija standardnog ulaza dana su dva prirodna broja N i M - broj redaka i stupaca matrice u tom test primjeru.

Opis izlaza

Za i-ti (za i = 1,2,\ldots, T) test primjer:

• ako ne postoji tražena matrica, ispisati -1
• u suprotnome, ispisati bilo koju matricu koja zadovoljava uvjete zadaće.

Primjer 1

Ulaz

2
1 6
4 4

Izlaz

-1
1 1 1 1
1 0 0 1
1 0 1 1
1 1 1 1

Objašnjenje

Može se pokazati kako ne postoji ni jedna matrica dimenzija N= 1, M = 6, koja zadovoljava uvjete zadaće.

U drugome primjeru, kada je N = M = 4, onda možemo vidjeti kako je zbroj brojeva:

• u prvom retku jednak 4, što je djeljivo s jedan
• u drugom retku jednak 2, što je djeljivo s dva
• u trećem retku jednak 3, što je djeljivo s tri
• u četvrtom retku jednak 4, što je djeljivo s četiri.

Također, možemo izračunati kako je zbroj brojeva:

• u prvom stupcu jednak 4, što je djeljivo s jedan
• u drugom stupcu jednak 2, što je djeljivo s dva
• u trećom stupcu jednak 3, što je djeljivo s tri
• u četvrtom stupcu jednak 4, što je djeljivo s četiri.

Time smo našli matricu koja zadovoljava uvjete.

Ograničenja

• 1 \leq T \leq 3
• 1 \leq N\cdot M \leq 1.000.000.

Test primjeri su podijeljeni u četiri disjunktne skupine:

• U test primjerima vrijednim 10 bodova, važi kako je NM \leq 20.
• U test primjerima vrijednim 10 bodova, važi kako je NM \leq 30.
• U test primjerima vrijednim 25 bodova, važi kako je NM \leq 45.
• U test primjerima vrijednim 55 bodova, nema dodatnih ograničenja.