CSES - Taideteos
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Uolevinismi on taidesuunta, jossa on kaksi sääntöä. Ensinnäkin taideteoksen tulee muodostua mustista viivoista valkoisella taustalla. Lisäksi mitkään kaksi viivaa eivät saa leikata.

Sinulle on annettu kuvaus taideteoksesta, ja tehtäväsi on selvittää, onko se uolevinismin mukainen.

Syöte

Syöteen ensimmäisellä rivillä on kokonaisluku t: testitapausten määrä. Sitten syötteessä on t testitapausta, jotka on kuvattu seuraavasti:

Ensimmäisellä rivillä on kokonaisluku n: viivojen määrä.

Tämän jälkeen syöteessä on n riviä, joista jokainen kuvaa yhden viivan. Rivillä on neljä kokonaislukua x_1, y_1, x_2 ja y_2. Tämä tarkoittaa, että viiva alkaa pisteestä (x_1,y_1) ja päättyy pisteeseen (x_2,y_2).

Jokainen viiva on musta ja teoksen tausta on valkoinen. Mitkään kaksi viivaa eivät ole samalla suoralla, eikä viivoilla ole yhteisiä päätepisteitä.

Tuloste

Tulosta jokaisesta testitapauksesta "10-4", jos taideteos on uolevinismin mukainen, ja muuten "QAQ".

Rajat

  • 1 \le t \le 100
  • 1 \le n \le 100
  • -10^6 \le x_1,y_1 \le 10^6
  • -10^6 \le x_2,y_2 \le 10^6

Esimerkki

Syöte:

3
2
1 3 4 3
3 1 3 4
3
1 2 2 4
2 2 3 3
2 1 4 2
4
2 2 3 3
2 3 3 2
2 4 3 5
2 5 3 4

Tuloste:

QAQ
10-4
QAQ