Trol

Ο Stjepan έλαβε πρόσφατα το πτυχίο του στα μαθηματικά από το Πανεπιστήμιο του Ζάγκρεμπ. Όπως είναι φυσικό, οι γονείς του είναι πολύ περήφανοι και αποφάσισαν να του κάνουν δώρο όλους τους θετικούς ακέραιους όχι μεγαλύτερους από 260. Για να τους κρατήσει ασφαλείς, αποθήκευσε γρήγορα όλους αυτούς τους αριθμούς σε έναν πίνακα ~A~, έτσι ώστε ~A_i = i~.

Ο ζηλιάρης φίλος του Marin αποφάσισε να του κάνει φάρσα αντικαθιστώντας επανειλημμένα κάθε στοιχείο του ~A~ με το άθροισμα των ψηφίων του έως ότου όλα τα στοιχεία του ~A~ αποτελούνταν από ένα μόνο ψηφίο. Για παράδειγμα, η αρχική τιμή του 197ου στοιχείου του ~A~ ήταν 197. Ο Marin άλλαξε πρώτα αυτήν την τιμή σε ~1 + 9 + 7 = 17~ και μετά άλλαξε την τιμή του ξανά σε ~1 + 7 = 8~.

Ο Stjepan είναι συντετριμμένος και παρακαλεί τον Marin να επιστρέψει τη σειρά του στην αρχική του κατάσταση. Δυστυχώς, ο Marin δεν θα το κάνει αυτό έως ότου ο Stjepan απαντήσει σωστά στις ερωτήσεις Q: "Ποιο είναι το άθροισμα των αριθμών από το l-οστό στο r-οστό στοιχείο του ~A~;"".

Βοηθήστε τον Stjepan να απαντήσει σε αυτά τα ερωτήματα!

Είσοδος

Η πρώτη γραμμή περιέχει έναν ακέραιο ~Q\;(1 \le Q \le 100)~ από την περιγραφή της εργασίας.
Οι επόμενες γραμμές ~Q~ περιέχουν δύο ακέραιους ~l_i~ και ~r_i\;(1 \le l_i \le r_i \le 2^{60})~, τις παραμέτρους του i-οστού ερωτήματος του Marin.

Έξοδος

Καταχωρίστε τις απαντήσεις σε καθένα από τα ερωτήματα ~Q~ του Marin. Κάθε απάντηση θα πρέπει να εκτυπώνεται σε ξεχωριστή γραμμή και η σειρά τους να ταιριάζει με τη σειρά των ερωτημάτων όπως δίνονται στην εισαγωγή.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις συνολικής αξίας 10 πόντων, για κάθε ερώτημα θα ισχύει ~1 \le l_i \le r_i \le 9~.
Σε δοκιμαστικές περιπτώσεις συνολικής αξίας 30 πόντων, για κάθε ερώτημα θα ισχύει ~r_i - l_i \le 1000~.

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

input

1
1 5

output

15

input

2
9 13
44 45

output

19
17

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

1o ερώτημα ~\rightarrow\;A_9 = 9,\;A_{10} = 1 + 0 = 1,\;A_11 = 1 + 1 = 2,\;A_12 = 1 + 2 = 3,\;A_13 = 1 + 3 = 4.\;A_9 + A_10 + A_11 + A_12 + A_13 = 9 + 1 + 2 + 3 + 4 = 19~.

2o ερώτημα ~\rightarrow\;A_44 = 4 + 4 = 8,\;A_45 = 4 + 5 = 9.\;A_44 + A_45 = 8 + 9 = 17~.

input

1
1998 2018

output

102