Mr Bin là một cậu bé đang học tiểu học, cậu thích tìm hiểu về số học. Cậu đang nghiên cứu một loại số mà cậu tạm gọi là số vui vẻ. Cậu định nghĩa rằng: một số nguyên dương ~n~ được gọi là số vui vẻ nếu tổng bình phương các chữ số của ~n~ là một số chẵn.

Ví dụ: ~123~ là số vui vẻ vì ~1^2+2^2+3^2=14~ là số chẵn, ngược lại ~32~ không phải số vui vẻ vì ~3^2+2^2=13~ là số lẻ.

Cậu băn khoăn tự hỏi liệu có bao nhiêu số vui vẻ trong đoạn ~[a, b]~ nhỉ? Nhờ bạn hãy giúp Mr Bin nhé!

Dữ liệu vào

• Dòng đầu chứa một số nguyên dương ~T~ ~(1 ≤ T ≤ 10^5)~ là số lượng test.
• ~T~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~a, b~ ~(1 ≤ a ≤ b ≤ 10^6)~.

Dữ liệu ra

• Với mỗi test, in ra số lượng số vui vẻ trong đoạn ~[a, b]~ trên một dòng.

Ví dụ

Giới hạn

• Có 50% số test có ~T, a, b ≤ 10^3~.