Tehtäväsi on etsiä n \times m -ruudukon vasemmasta yläkulmasta alkava reitti, joka muodostuu hypyistä. Reitin tulee käydä tasan kerran jokaisessa ruudussa, ja jokaisen hypyn tulee olla erilainen.

Jokainen reitin hyppy voidaan esittää parina (y,x), jossa kokonaisluvut y ja x ilmaisevat siirtymän pysty- ja vaakasuunnassa. Koordinaatit kasvavat ylhäältä alaspäin ja vasemmalta oikealle. Esimerkiksi (2,-1) tarkoittaa hyppyä kaksi askelta alaspäin ja yksi askel vasemmalle.

Esimerkiksi 2 \times 3 -ruudukossa yksi mahdollinen hyppely on seuraava:

Tässä tapauksessa hypyt ovat järjestyksessä (1,0), (0,2), (-1,-1), (0,1), (1,-1). Ratkaisu on kelvollinen, koska jokainen hyppy on erilainen.

Syöte

Ensimmäisellä rivillä on kokonaisluku t: testien määrä.

Jokaisella seuraavalla rivillä on kaksi kokonaislukua n ja m: ruudukon korkeus ja leveys.

Tuloste

Jokaisessa testissä tulosta ratkaisuna n \cdot m - 1 lukua, jotka ilmaisevat järjestyksessä kunkin hypyn siirtymän pysty- ja vaakasuunnassa.

Jos mahdollisia ratkaisuja on useita, voit tulostaa minkä tahansa niistä. Tehtävään on olemassa aina ratkaisu.

Esimerkki

Syöte:

4
1 1
2 2
1 3
2 3

Tuloste:

0 1
1 0
0 -1
0 2
0 -1
1 0
0 2
-1 -1
0 1
1 -1

Huomaa, että ensimmäisessä testissä reitissä ei ole yhtään hyppyä, koska ruudukossa on vain yksi ruutu.

Osatehtävä 1 (30 pistettä)

• 1 \le t \le 100
• 1 \le n, m \le 5

Osatehtävä 2 (70 pistettä)

• 1 \le t \le 100
• 1 \le n, m \le 50