Pictionary

Υπάρχει ένας πλανήτης, σε ένα ακόμη άγνωστο μέρος του σύμπαντος, με μια χώρα που κατοικείται αποκλειστικά από μαθηματικούς. Σε αυτή τη χώρα, υπάρχουν συνολικά ~N~ μαθηματικοί και το ενδιαφέρον γεγονός είναι ότι κάθε μαθηματικός ζει στη δική του πόλη. Είναι επίσης ενδιαφέρον το γεγονός ότι δεν υπάρχουν δύο πόλεις που να συνδέονται με έναν δρόμο, επειδή οι μαθηματικοί μπορούν να επικοινωνούν διαδικτυακά ή εξετάζοντας ακαδημαϊκές εργασίες. Φυσικά, οι πόλεις είναι αριθμημένες με αριθμούς από το 1 έως το \(Ν\).

Η ζωή ήταν τέλεια μέχρι που ένας μαθηματικός αποφάσισε να γράψει μια ακαδημαϊκή εργασία στο smartphone του. Το smartphone διόρθωσε αυτόματα τη λέξη "αυτονόητο" σε "Pictionary" και το aper δημοσιεύτηκε ως τέτοιο. Αμέσως μετά, ολόκληρη η χώρα ανακάλυψε το Pictionary και θέλησε να συναντηθούνε και να παίξουνε, έτσι οι εργασίες κατασκευής δρόμων μεταξύ των πόλεων ξεκίνησαν σύντομα.

Η οδοποιία θα διαρκέσει συνολικά \(Μ\) ημέρες, σύμφωνα με το ακόλουθο χρονοδιάγραμμα: την πρώτη ημέρα, η κατασκευή γίνεται σε δρόμους μεταξύ όλων των ζευγών πόλεων που έχουν το Μ ως μεγαλύτερο κοινό διαιρέτη. Τη δεύτερη ημέρα, η κατασκευή γίνεται σε δρόμους μεταξύ όλων των ζευγών πόλεων που έχουν το \(Μ-1\) ως τον μεγαλύτερο κοινό διαιρέτη και ούτω καθεξής μέχρι τη \(Μ\)-οστή ημέρα που γίνεται η κατασκευή σε δρόμους μεταξύ όλων των ζευγών πόλεων που είναι σχετικά πρώτοι. Πιο επίσημα, την ~i~-οστή ημέρα, η κατασκευή γίνεται σε δρόμους μεταξύ των πόλεων ~a~ και ~b~ εάν \(ΜΚΔ(a, b) = M-i+1\).

Εφόσον οι μαθηματικοί είναι απασχολημένοι με οικοδομικές εργασίες, σας ζήτησαν να τους βοηθήσετε να προσδιορίσουν τον ελάχιστο αριθμό ημερών πριν ένα δεδομένο ζευγάρι μαθηματικών μπορεί να παίξει Pictionary μαζί.

Είσοδος

Η πρώτη γραμμή εισαγωγής περιέχει τρεις θετικούς ακέραιους ​~N, M~ και ~Q~ \((1 \le N, ​Q \le 100.000, 1 \le M \le N)\), τον αριθμό των πόλεων, τον αριθμό των ημερών χρειάζεται για την κατασκευή των δρόμων και τον αριθμό των ερωτημάτων.

Κάθε μία από τις ακόλουθες γραμμές Q περιέχει δύο διακριτούς θετικούς ακέραιους αριθμούς ~A~ και ~B~ ~(1 \le A, B \le N)~ που δηλώνουν τις πόλεις των μαθηματικών που θέλουν να μάθουν τον ελάχιστο αριθμό ημερών πριν μπορούν να παίξουν Pictionary μαζί.

Έξοδος

Η γραμμή i πρέπει να περιέχει τον ελάχιστο αριθμό ημερών προτού οι μαθηματικοί από το ι-οστό αίτημα μπορούν να παίξουν Pictionary μαζί.

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας 40% των συνολικών πόντων, θα ισχύει \(N​\le 1.000, Q \le 100.000.\)

Παραδείγματα

input

8 3 3
2 5
3 6
4 8

output

3
1
2

Επεξήγηση του 1ου παραδείγματος:

Την πρώτη μέρα κατασκευάζεται δρόμος (3, 6). Επομένως η απάντηση στο δεύτερο ερώτημα είναι 1.
Τη δεύτερη μέρα κατασκευάζονται οι δρόμοι (2, 4), (2, 6), (2, 8), (4, 6) και (6, 8). Οι πόλεις 4 και 8 είναι πλέον συνδεδεμένες (είναι δυνατό να φτάσετε από την πρώτη στη δεύτερη χρησιμοποιώντας την πόλη 6).
Την τρίτη ημέρα, χτίζονται δρόμοι μεταξύ σχετικά πρώτων πόλεων, έτσι οι πόλεις 2 και 5 συνδέονται.

input

25 6 1
20 9

output

4

Επεξήγηση του 2ου παραδείγματος:

Τη δεύτερη μέρα κατασκευάζεται ο δρόμος (20, 15), ενώ την τέταρτη μέρα ο δρόμος (15, 9). Μετά την τέταρτη ημέρα, οι πόλεις 20 και 9 συνδέονται μέσω της πόλης 15.

input

9999 2222 2
1025 2405
3154 8949

output

1980
2160