Chewbacca

Σας δίνεται ένα δέντρο τάξης \(Κ\) με \(Ν\) κόμβους ή, με άλλα λόγια, κάθε κόμβος μπορεί να έχει το πολύ ~K~ παιδιά. Το δέντρο είναι κατασκευασμένο έτσι ώστε να έχει τη "χαμηλότερη ενέργεια": οι κόμβοι τοποθετούνται σε ένα νέο βάθος του δέντρου μόνο όταν έχουν συμπληρωθεί όλες οι θέσεις (από αριστερά προς τα δεξιά) στο προηγούμενο βάθος. Αυτή είναι επίσης η σειρά απαρίθμησης των κόμβων, ξεκινώντας από το 1. Η εικόνα απεικονίζει ένα παράδειγμα δέντρου τάξης 3 με 9 κόμβους.

Πρέπει να εξάγετε απαντήσεις σε ~Q~ ερωτήματα με τη μορφή ~x~ ~y~, όπου η απάντηση είναι ο ελάχιστος αριθμός βημάτων που απαιτούνται για να φτάσετε από τον κόμβο ~x~ στον κόμβο ~y~.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τους ακέραιους αριθμούς ~N\;(1 \leq N \leq 10^{15} ),\;K\;(1 \leq K \leq 1\,000)~ και ~Q\;(1 \leq Q \leq 100\,000)~.
Κάθε μία από τις ακόλουθες γραμμές ~Q~ περιέχει ζεύγη ~xy\;(1 \leq x,y \leq N,\;x \neq y)~.

Έξοδος

Τυπώστε ~Q~ γραμμές, με κάθε γραμμή να περιέχει την απάντηση σε ένα ερώτημα από την εργασία.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας ~20~% των συνολικών πόντων, θα έχει ~1 \leq N,\;Q \leq 1\,000~.
Σε περιπτώσεις δοκιμής αξίας ~50~% των συνολικών πόντων, θα έχει ~1 \leq N,\;Q \leq 100\,000~.

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

input

7 2 3
1 2
2 1
4 7

output

1
1
4

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

Σας δίνεται ένα πλήρες δυαδικό δέντρο. Ο κόμβος 2 είναι άμεσο παιδί του κόμβου 1, επομένως η απόσταση μεταξύ τους είναι ακριβώς 1. Οι κόμβοι 4 και 7 βρίσκονται σε εντελώς αντίθετες πλευρές του δέντρου, επομένως η απόσταση μεταξύ τους είναι 4: ~4 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 7~.

input

9 3 3
8 9
5 7
8 4

output

2
2
3

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

Αυτό το παράδειγμα αντιστοιχεί στην εικόνα.