38ος ΠΔΠ Α' Φάση
Δυαδικά ερωτήματα (bqueries)

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

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

\[x\texttt{ AND }y = x\]

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

Δεδομένα εισόδου (stdin)

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

Δεδομένα εξόδου (stdout)

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

Παράδειγμα εισόδου-εξόδου

stdin	stdout
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 \leq Q \leq 200.000\),
\(0 \leq L_i \leq R_i \leq 10^9\).

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

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

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

Μέγιστος χρόνος εκτέλεσης: \(2\) sec.
Μέγιστη διαθέσιμη μνήμη: \(64\) MB.