San

Η Anica βλέπει ένα περίεργο όνειρο. Ονειρεύεται ένα άπειρο ταμπλό. Σε αυτό το ταμπλό, σχεδιάζεται ένας άπειρος πίνακας που αποτελείται από άπειρες γραμμές και άπειρες στήλες που περιέχουν άπειρους αριθμούς. Είναι ενδιαφέρον ότι κάθε αριθμός στον πίνακα εμφανίζεται πεπερασμένος αριθμός φορών.

Ο πίνακας έχει εξαιρετικά κανονικό σχήμα και οι τιμές του ικανοποιούν τις απαιτήσεις μιας απλής αναδρομικής σχέσης. Το πρώτο κελί κάθε σειράς περιέχει τον τακτικό αριθμό αυτής της σειράς. Μια τιμή ενός κελιού που δεν βρίσκεται στην πρώτη στήλη μπορεί να υπολογιστεί αθροίζοντας τον αριθμό στο κελί στα αριστερά του και τον ίδιο αριθμό, μόνο γραμμένο αντίστροφα (σε δεκαδική αναπαράσταση).

Τυπικά, αν το \(A(i,\j)\) υποδηλώνει την τιμή στην i-οστή σειρά και την j-οστή στήλη, ισχύει:

• ~A(i,\;1) = i~
• ~A(i,\;j) = A(i,\;j - 1) + rev^1(A(i,\;j - 1))~, για κάθε ~j > 1~

1	2	4	8	16	77	154
2	4	8	16	77	154	605
3	6	12	33	66	132	363	~\cdots~
4	8	16	77	154	605	1111
5	10	11	22	44	88	176
				~\vdots~			~\ddots~

Η Anica δεν έχει δείξει πολύ ενδιαφέρον για το ταμπλό και το προσπέρασε. Πίσω από τον πίνακα, παρατήρησε μια λάμπα που τράβηξε αμέσως την προσοχή της. Η Anica τράβηξε επίσης την προσοχή της λάμπας, οπότε το φιλικό φάντασμα Božo βγήκε από μέσα.

"Anica! Εάν απαντήσεις σωστά στα ~Q~ ερωτήματά μου, θα κερδίσετε ένα πακέτο γκοφρέτα Dorina ή μπισκότα Domaćica, με βάση τη δική σας επιλογή! Δεν θα ήθελα να επιβάλω τη στάση μου, αλλά κατά την προσωπική μου άποψη, τα μπισκότα γκοφρέτας Dorina είναι καλύτερα. Κάθε ερώτημα θα αποτελείται από δύο ακέραιους αριθμούς ~A~ και ~B~. Πρέπει να απαντήσετε πόσες εμφανίσεις αριθμών του διαστήματος ~[A,\;B]~ υπάρχουν στον πίνακα."

Δυστυχώς, η Anica δεν μπόρεσε να απαντήσει στις ερωτήσεις και ξύπνησε.

"Α, δεν κέρδισα τα μπισκότα Dorina, αλλά τουλάχιστον έχω μια δουλειά για την COCI", σκέφτηκε και συνέχισε την επιχείρησή της.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο αριθμό ~Q\;(1 \leq Q \leq 10^5)~, τον αριθμό των ερωτημάτων.
Κάθε μία από τις ακόλουθες ~Q~ γραμμές περιέχει δύο ακέραιους αριθμούς ~A~ και ~B\;(1 \leq A \leq B \leq 10^{10})~ που αντιπροσωπεύουν το διάστημα από το ερώτημα.

Έξοδος

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

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας 50% των συνολικών πόντων, θα ισχύει ~(1 \leq A, B \leq 10^6 )~.

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

input

2
1 10
5 8

output

18
8

input

3
17 144
121 121
89 98

output

265
25
10

input

1 1000000000

output

1863025563