Sau ngày thi thứ nhất, ~Quốc~ rất vui vẻ vì mình làm bài rất tốt. Với động lực đó, ~Quốc~ cà ng hăng say học tập. Hôm nay, ~Quốc~ bắt tay vào nghiên cứu số Fibonaci.

Sử dụng công thức tổng quát của dãy số ~Fibonaci~ :

~F_n = \begin{cases} 1 &\text{ nếu } n \le 2 \\ F_{n-1}+F_{n-2} &\text{nếu } n \geq 3 \end{cases}~

~Quốc~ lần lượt tính các số của dãy số ~Fibonaci~ và viết chúng cạnh nhau từ trái qua phải tạo thành một dãy số vô hạn: ~112358132134...~

~Quốc~ có một câu hỏi: với dãy số vô hạn được tạo bằng cách trên , thì chữ số tính từ trái qua phải là chữ số nào. Bạn hãy lập trình giúp ~Quốc~ trả lời câu hỏi trên.

Cho 2 số ~l~ và ~r~, hãy in ra tất cả chữ số tính từ ~l~ và ~r~ của dãy số vô hạn mà ~Quốc~ tạo ra.

Input

Dòng đầu là ~Q~ truy vấn ~(1 \le Q \le 100)~

~Q~ dòng tiếp theo gồm ~2~ số nguyên ~l~ ~r~ ~(1 \le l < r \le 10^7)~

Output

In ra các chữ số tính từ ~l~ và ~r~ của dãy số vô hạn mà ~Quốc~ tạo ra

Sample Input

3
1 3
4 7
7 9

Sample Output

112
3581
132