Osumnjičeni

Σε μια αστυνομική έρευνα, εντοπίστηκαν ~n~ ύποπτοι και τώρα εναπόκειται στους μάρτυρες να προσπαθήσουν να βρουν τον δράστη. Μετρήθηκε το ύψος κάθε υπόπτου ~i~, αλλά λόγω της αναξιοπιστίας της μέτρησης, είναι γνωστό μόνο ότι το ύψος τους είναι ένας πραγματικός αριθμός που βρίσκεται στο διάστημα από ~l_i~ έως ~r_i~ (κλειστό διάστημα). Το πολύ ένας από τους υπόπτους είναι ο δράστης, δηλαδή υπάρχει η πιθανότητα να μην είναι κανένας από αυτούς.

Μια σειρά υπόπτων αποτελείται από την επιλογή δύο θετικών ακέραιων αριθμών ~a~ και ~b~ ~(1 \le a \le b \le n)~ και στη συνέχεια μεταφέρονται οι υπόπτοι ~a,\;a + 1,\;\ldots,\;b~ σε ξεχωριστό δωμάτιο, ώστε οι μάρτυρες να προσπαθήσουν να αναγνωρίσουν τον δράστη. Καθώς οι μάρτυρες θα μπορούσαν να μπερδευτούν εάν δύο από τους υπόπτους έχουν το ίδιο ύψος, μια σειρά υπόπτων επιτρέπεται μόνο εάν είναι δυνατό να διασφαλιστεί ότι κανένας ύποπτος δεν έχει το ίδιο ύψος με κάποιον άλλον. Κατά τη διάρκεια εμφάνισης μιας σειράς υπόπτων, οι μάρτυρες θα είναι πάντα σε θέση να αναγνωρίσουν τον δράστη εάν είναι μεταξύ των επιλεγμένων υπόπτων ή θα μπορούν να πουν ότι δεν είναι ανάμεσά τους.

Ο κύριος ερευνητής ενδιαφέρεται τώρα να απαντήσει σε ερωτήσεις της ακόλουθης μορφής: "Αν ήμουν σίγουρος ότι ο αριθμός του δράστη θα μπορούσε να είναι μόνο μεταξύ ~p~ και ~q~ ~(p \le q)~, ποιος είναι ο ελάχιστος αριθμός σειρών υπόπτων που απαιτούνται στη χειρότερη περίπτωση ώστε οι μάρτυρες να μπορέσουν να βρουν τον δράστη ή να αναφέρουν ότι δεν είναι μεταξύ των υπόπτων;". Βοηθήστε τον ερευνητή που είναι επικεφαλής να απαντήσει ~q~ τέτοιες ερωτήσεις.

Είσοδος

Η πρώτη γραμμή περιέχει έναν θετικό ακέραιο ~n~, τον αριθμό των υπόπτων.

Οι ακόλουθες ~n~ γραμμές περιέχουν δύο θετικούς ακέραιους αριθμούς ~l_i~ και ~r_i~ ~(1 \le l_i \le r_i \le 10^9)~ που αντιπροσωπεύουν το πιθανό εύρος ύψους του ύποπτου με αριθμό ~i~.

Η επόμενη γραμμή περιέχει έναν θετικό ακέραιο ~q~, τον αριθμό των ερωτήσεων.

Οι παρακάτω ~q~ γραμμές περιέχουν δύο θετικούς ακέραιους ~p_i~ και ~q_i~ ~(1 \le p_i \le q_i \le n)~ που καθορίζουν μια ερώτηση.

Έξοδος

Σε ~q~ γραμμές εκτυπώστε τις απαντήσεις στις αντίστοιχες ερωτήσεις: τον ελάχιστο απαιτούμενο αριθμό σειρών υπόπτων.

Βαθμολογία

Σε κάθε υποπρόβλημα ισχύει ότι ~1 \le n, q \le 200\,000~.

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	10	~q = 1,\;p_1 = 1,\;q_1 = n~
2	10	~1 \le n \le 5000,\;1 \le q \le 5000~
3	20	~1 \le n \le 5000,\;1 \le q \le 200\,000~
4	20	~1 \le n \le 200\,000,\;1 \le q \le 100~
5	50	Κανένας επιπλέον περιορισμός.

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

input

2
1 1
1 1
3
1 1
2 2
1 2

output

1
1
2

input

3
1 1
2 2
3 3
3
1 1
2 3
1 3

output

1
1
1

input

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

output

3
1
3

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

Για την πρώτη και την τρίτη ερώτηση, αρκεί να έχουμε τρεις σειρές υπόπτων: μία αποτελείται από τον ύποπτο 1, μία από τους υπόπτους 2 και 3 και μία από τους υπόπτους 4 και 5.

Για τη δεύτερη ερώτηση, αρκεί να υπάρχει μια σειρά υπόπτων που αποτελείται από τους υπόπτους 3, 4 και 5.