Trong quá trình nghiên cứu các hệ thống mật mã dựa trên đặc trưng chữ số, các chuyên gia đã định nghĩa một lớp số nguyên đặc biệt gọi là số lõi kép.

Một số nguyên dương ~x~ được gọi là số lõi kép nếu:

• Gọi ~s(x)~ là tổng các chữ số của ~x~ trong hệ thập phân
• Gọi ~p(x)~ là tổng bình phương các chữ số của ~x~ trong hệ thập phân.
• ~x~ được gọi là số lõi kép nếu nó thỏa mãn điều kiện: $$x \pmod{s(x)^4 + p(x)^2} = 0$$

Cho ~T~ truy vấn, mỗi truy vấn gồm hai số nguyên ~L~ và ~R~, hãy đếm số lượng số lõi kép nằm trong đoạn từ ~L~ đến ~R~.

Input

• Dòng đầu tiên chứa số nguyên dương ~T~ (~1 \le T \le 10~) — số lượng truy vấn.
• ~T~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~L~ và ~R~ (~1 \le L \le R \le 2 \cdot 10^9~) mô tả một truy vấn.

Output

~T~ dòng, mỗi dòng chứa một số nguyên là kết quả của truy vấn tương ứng.

Sample Input

1
5 20

Sample Output

1

Chỉ có một số thỏa mãn là số ~10~, vì ~10~ chia hết cho (~1^4 + 1^2 = 2~).

Ngoài ra, số ~12002~ cũng thỏa mãn vì ~12002~ chia hết cho (~5^4 + 9^2 = 706~).