Một số nguyên dương được gọi là số siêu lẻ nếu bản thân nó là số lẻ và tổng các chữ số của nó cũng là số lẻ.

Cho ~M~ truy vấn, mỗi truy vấn gồm hai số ~a,b~. Cần đếm số siêu lẻ trong đoạn ~[a,b]~.

Input

• Dòng đầu chứa số nguyên dương ~M~ ~(M \le 10^6)~.
• ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~a,b~ ~(1 \le a \le b \le 10^6)~.

Output

In ra ~M~ dòng, mỗi dòng là đáp án của truy vấn tương ứng.

Subtask

• Subtask ~1~ có ~70\%~ số điểm: ~M=1~.
• Subtask ~2~ có ~30\%~ số điểm: không có ràng buộc gì thêm.

Ví dụ 1

1
7 24

4

Ví dụ 2

2
30 39
286 315

0
5