Δυαδικά ερωτήματα

Κουρασμένος από το κουβάλημα των κουτιών από την αποθήκη του Γιάννη πίσω στη δική του, ο Τάκης έκατσε στο γραφείο του για να προσπαθήσει να σκεφτεί ένα θέμα για την Α' Φάση του ΠΔΠ. Πάνω στις δοκιμές που έκανε στο χαρτί του παρατήρησε ότι ~5~ ~AND~ ~4 = 4~ όπου ~AND~ η bitwise πράξη KAI (δείτε εδώ τον ορισμό της). Αυτό του φάνηκε πολύ ενδιαφέρον και θέλησε να μάθει πόσο συχνά ισχύει ότι το bitwise ~AND~ δύο αριθμών ισούται με έναν από αυτούς.

Συγκεκριμένα έχει ~Q~ ερωτήματα της μορφής ~(L,\;R)~, όπου ~L~ και ~R~ είναι μη αρνητικοί ακέραιοι και ~L \le R~. Η απάντηση ενός τέτοιου ερωτήματος είναι το πλήθος ζευγών ~(x,\;y)~ τέτοιων ώστε ~L \le x \le R~ και ~L \le y \le R~, για τα οποία ισχύει:

~x\;AND\;y = x~

Απαντήστε τα ερωτήματα του Τάκη, όσο αυτός ψάχνει να βρει ενδιαφέροντα θέματα και για την Β' Φάση.

Πρόβλημα

Να γράψετε ένα πρόγραμμα σε μία από τις γλώσσες του ΠΔΠ (PASCAL, C, C++, JAVA) το οποίο θα διαβάζει τα δεδομένα εισόδου από το αρχείο bqueries.in και θα εκτυπώνει τα αποτελέσματα στο αρχείο bqueries.out.

Αρχεία εισόδου (bqueries.in)

Η πρώτη γραμμή περιέχει έναν ακέραιο αριθμό ~Q~: το πλήθος των ερωτημάτων του Τάκη. Ακολουθούν ~Q~ γραμμές, καθεμία από τις οποίες περιέχει δύο ακέραιους αριθμούς ~L_i~ και ~R_i~: το ~i~-οστό ερώτημα.

Αρχεία εξόδου (bqueries.out)

Πρέπει να αποτελείται από ~Q~ γραμμές, καθεμία από τις να περιέχει έναν ακέραιο αριθμό: την απάντηση στο ~i~-οστό ερώτημα.

Παράδειγμα αρχείων εισόδου - εξόδου:

Είσοδος:

2
3 7
777777 888888

Έξοδος:

11
75497532

Εξήγηση:

Για το πρώτο ερώτημα, τα ~11~ ζεύγη ακεραίων από ~3~ έως και ~7~ που ικανοποιούν το ζητούμενο είναι: ~(3,\;3)~, ~(3,\;7)~, ~(4,\;4)~, ~(4,\;5)~, ~(4,\;6)~, ~(4, \;7)~, ~(5,\;5)~, ~(5,\;7)~, ~(6,\;6)~, ~(6,\;7)~ και ~(7,\;7)~.

Περιορισμοί

• ~1 \le Q \le 200.000~
• ~0 \le L_i \le R_i \le 10^9~

Υποπροβλήματα:

1. (13 βαθμοί) ~L_i = 0~, ~R_i \le 5000~, για κάθε ~i~ (όπου ~1 \le i \le Q~).
2. (16 βαθμοί) ~L_i = 0~, ~R_i \le 200.000~, για κάθε ~i~ (όπου ~1 \le i \le Q~).
3. (21 βαθμοί) Για κάθε ~i~ (όπου ~1 \le i \le Q~), υπάρχουν θετικοί ακέραιοι ~k~, ~m~ τέτοιοι ώστε ~L_i = 2^k~ και ~R_i = 2^m - 1~
4. (27 βαθμοί) ~L_i = 0~, για κάθε ~i~ (όπου ~1 \le i \le Q~).
5. (23 βαθμοί) Δεν υπάρχουν περαιτέρω περιορισμοί.

Παρατηρήσεις:

• Μορφοποίηση: Στην είσοδο αλλά και στην έξοδο, κάθε γραμμή τερματίζει με έναν χαρακτήρα newline.
• Μέγιστος χρόνος εκτέλεσης: ~2~ sec.
• Μέγιστη διαθέσιμη μνήμη: ~64~ MB.
• Επικεφαλίδες στον πηγαίο κώδικα: Στην αρχή του πηγαίου κώδικά σας, θα πρέπει να χρησιμοποιήσετε τις παρακάτω επικεφαλίδες.

(* USER: username
LANG: PASCAL
TASK: bqueries *)

για κώδικα σε PASCAL

/* USER: username
LANG: C
TASK: bqueries */

για κώδικα σε C

/* USER: username
LANG: C++
TASK: bqueries */

για κώδικα σε C++

/* USER: username
LANG: Java
TASK: bqueries */

για κώδικα σε Java

Προσοχή: Η απάντηση μπορεί να υπερβαίνει το ~2^{32}~. Επίσης, φροντίστε να διαβάζετε την είσοδο και να εκτυπώνετε την έξοδο αποδοτικά, ειδικά αν μεταφράζετε σε C++ ή Java.