Transforming Comets

Όταν ταξίδευε από τη Γη στο Κρύπτον, ο Σούπερμαν πιάστηκε σε μια σκουληκότρυπα και μεταφέρθηκε αμέσως σε κάποια άγνωστη τοποθεσία. Ο Σούπερμαν θυμάται ότι είδε περιοδικούς κομήτες από τη Γη, και μπορεί να δει μερικούς περιοδικούς κομήτες από την τρέχουσα θέση του. Θα ήθελε να χρησιμοποιήσει αυτούς τους κομήτες για να βρει τον προσανατολισμό του, αλλά πρώτα πρέπει να ταιριάξει ποιός είναι ποιός.

Οι συγκεκριμένοι κομήτες που βλέπει ο Σούπερμαν είναι περιοδικοί Gaussian υπερ-κομήτες. Ένας περιοδικός Gaussian υπερκομήτης είναι μια ακολουθία (~p_1, p -2, ... , p_n~) όπου κάθε ~p_i~ είναι ένα δισδιάστατο σημείο (~x_i, y_i~) με ακέραιες συντεταγμένες. Ο κομήτης επισκέπτεται κάποιο σημείο ~p_i~ και μετά επισκέπτεται το σημείο ~p_{i+1}~. Η ακολουθία είναι περιοδική: μετά την επίσκεψη στο ~p_n~ ο κομήτης επισκέπτεται το ~p_1~ στη συνέχεια (έτσι οι δείκτες ερμηνεύονται ως υπόλοιπο ακέραιας διαίρεσης με το ~n~ (modulo ~n~)). Οι Gaussian υπερκομήτες έχουν επίσης την ειδική ιδιότητα ότι ~p_i \ne p_{i+1}~ για κάθε ~i~ και ~p_1 \ne p_n~.

Ο Σούπερμαν ήταν αποπροσανατολισμένος τόσο στον χώρο όσο και στον χρόνο. Όσον αφορά τον χώρο αυτό σημαίνει έναν κομήτη που είδε πριν μπορεί τώρα να έχει ολόκληρο το σύνολο σημείων του να περιστραμμένο, με τους δύο άξονες να κλιμακώνονται κατά τον ίδιο θετικό παράγοντα ή/και ερμηνευμένο. Επιπλέον, αφού αποπροσανατολίστηκε στο χρόνο, το πρώτο σημείο ενός κομήτη που ήξερε μπορεί να μην είναι πλέον το πρώτο σημείο.

Για παράδειγμα, ο ορθογώνιος τρίγωνος υπερκομήτης ((~0, 0~), (~1, 0~), (~0, 1~)) από τη γη μπορεί να μοιάζει με ((~40, 40~), (~20, 20~), (~60, 20~)) ή ((~20, 20~), (~60, 20~), (~40, 40~)). Σημειώστε ότι η αντιστροφή του χρόνου ή χώρου είναι μη επιτρεπόμενος μετασχηματισμός, π.χ. δεν είναι δυνατόν αυτός ο υπερ-κομήτης να εμφανίζεται ως ((~0, 1~), (~1, 0~), (~0, 0~)).

Ο στόχος σας είναι: δεδομένης μιας περιοδικής ακολουθίας σημείων που αντιστοιχούν σε έναν Gaussian υπερκομήτη που ο Σούπερμαν είδε από τη γη και σε έναν Gaussian υπερκομήτη που ο Σούπερμαν βλέπει τώρα, καθορίστε εάν θα μπορούσε να είναι ο ίδιος κομήτης.

Είσοδος

Η πρώτη γραμμή περιέχει ~1 \le t \le 10~, τον αριθμό των περιπτώσεων ελέγχου που ακολουθούν.

Κάθε περίπτωση ελέγχου ξεκινά με έναν ακέραιο ~n~ όπου ~2 \le n \le 500\,000~. Οι επόμενες ~n~ γραμμές, για ~i~ από το ~1~ στο ~n~, καθεμία περιέχουν, ένα, χωρισμένο με κενό, ζεύγος ακέραιων ~x_i~ ~y_i~. Αυτές οι γραμμές δηλώνουν τα σημεία μιας ακολουθίας που φαίνεται από τη Γη. Μετά, παρόμοια, υπάρχουν ~n~ επιπλέον γραμμές με καθεμία να περιέχει ένα ζεύγος από ακέραιους ~x_i~' ~y_i~'. Αυτές οι γραμμές δηλώνουν τα σημεία μιας ακολουθίας που φαίνεται από την τρέχουσα θέση του Σούπερμαν.

Είναι εγγυημένο ότι όλες οι συντεταγμένες είναι ακέραιοι που ανήκουν στο κλειστό διάστημα [~0, 30\,000~].

Έξοδος

Για κάθε περίπτωση ελέγχου, αν οι δύο ακολουθίες θα μπορούσαν να αναπαριστούν τον ίδιο υπερκομήτη υπό αυτή την διαδικασία αποπροσανατολισμού, εκτυπώστε τον μικρότερο θετικό ακέραιο ~s~ έτσι ώστε το ~x_1~ ~y_1~ να μπορεί να αντιστοιχεί στο ~x_s~' ~y_s~'. Αν δεν υπάρχει τέτοιο ~s~, εκτυπώστε ~0~.

Παράδειγμα

input

3
3
0 0
1 0
0 1
20 20
60 20
40 40
4
0 0
1 1
0 0
1 1
30 30
19 23
30 30
19 23
4
0 0
1 0
1 1
0 1
0 0
2 0
2 1
0 1

output

3
1
0