Ở vũ trụ song song này, người đứng đầu Terran lại là 1 bản sao của Đại úy Phillipa Georgiou (đã nhắc đến ở trên), dẫn dắt cả đội quân hùng mạnh giết chóc và cướp bóc khắp mọi nơi. Phillipa cùng đội quân của bà ta có 1 trụ sở gọi là Cung điện bay, nó to gấp nghìn lần những tàu vũ trụ khác và sử dụng tận gốc năng lượng bào tử để duy trì hoạt động, chế tạo vũ khí và gây ảnh hưởng đến mạng lưới sợi nấm trên đa vũ trụ.

Ở thế giới này, Michael Burnham là cánh tay phải của bà ta, lợi dụng điều đó* Michael* đã tìm cách len lỏi vào để lật đổ đế chế Terran, mang lại hòa bình cho vũ trụ này và làm sạch mạng lưới sợi nấm. Vậy nhưng, trong lúc ấy cô vô tình phát hiện ra hạm trưởng của mình Gabriel Lorca(đã nhắc đến ở trên) là Terran-er, ông đã từng nuôi hy vọng đạp đổ Phillipa và chiếm lĩnh đế chế Terran nhưng không thành công. Bằng một cách nào đó ông ta lại bị rơi vào thế giới kia, ông muốn lợi dụng động cơ bào tử để quay trở lại thế giới của mình và tiếp tục kế hoạch thống trị.

Các đồng đội trên tàu của Michael đã hỗ trợ rất tốt cho cô ấy bằng cách lên kế hoạch đặt boom để phá hủy* cung điện bay*. Về phía Michael, cũng là một người khá trọng nghĩa, khi quả boom gần phát nổ, cô đã chớp lấy thời cơ để đưa Phillipa dịch chuyển về USS Discovery. Đã gần như tiêu diệt hoàn toàn được đế chế Terran, việc bây giờ là đưa Discovery trở về đúng vũ trụ của nó, và cũng là nơi xuất phát của Michael và những người khác.

Khi Michael dẫn theo Phillipa về, trung úy Paul đã tìm lại được tọa độ ở vũ trụ cũ trước khi lạc sang thế giới này. Và .... nhảy. Anh ấy cứ rẽ trái, rẽ phải, rồi lại rẽ trái. Lần này con đường trong mạng lưới sợi nấm dường như dài hơn rất nhiều, dù biết trước tọa độ ở các ngã rẽ sẽ có dạng ~dx[i] = dx[i-1] + dx[i-2]~ nhưng anh không lường trước việc con đường về nhà lại xa đến vậy. Các bạn hãy giúp anh ấy cùng phi hành đoàn về đến quê hương của mình nhé.

Yêu cầu

Cho ~L, R (L \leq R)~, hãy tính tổng các chữ số cuối cùng của các ~dx[i]~ với ~L \leq i \leq R~. Bởi vì tổng này có thể rất lớn nên bạn chỉ cần in ra chữ số cuối cùng của nó.

Biết ~dx[1] = dx[2] = 1~

Input:

Dòng đầu tiên là ~T~, biểu thị số test.

Mỗi test gồm ~2~ số ~L~ và ~R~.

Output:

Gồm ~T~ dòng in ra chữ số cuối của tổng các chữ số cuối cùng của ~dx[i]~ với ~L <= i <= R~.

Tính điểm:

Subtasks: Mỗi subtask chiếm ~25~% số test.

Subtask 1: ~T ≤ 10;~ ~l, r \leq 10^6~

Subtask 2: ~T ≤ 10~^~4~~; l = r ≤ 10~^~18~

Subtask 3: ~T ≤ 10~^~4~~; l = 1, r ≤ 10~^~18~

Subtask 4: ~T ≤ 10~^~4~~;~ ~l~ ~,~ ~r ≤ 10~^~18~

Ví dụ:

Input 1

3
1 5
2 4
3 6

Output 1

2
6
8

Input 2

2
2 10
4 4

Output 2

2
3

Giải thích

10 ~dx[i]~ đầu tiên là ~1, 1, 2, 3, 5, 8, 13, 21, 34, 55~

Note: Nếu bạn thấy quá khó khăn, vì thuong_chirox9 là một người đáng iu (không phải như HMD) nên đã cho bạn một số gợi ý .