Bờm viết số 293 sau đó tính tổng bình phương các chữ số của số này và lấy kết quả đó thay thế cho số hiện tại: ~2^2 + 9^2 + 3^2 = 94~. Bờm tiếp tục lặp lại quá trình trên đến khi nhận được số 1 thì dừng: ~94 \to 97 \to 130 \to 10 \to 1~. Bờm gọi những số khi thực hiện quá trình như trên mà kết quả cuối cùng là số 1 là số đặc biệt. Bờm muốn biết trong đoạn ~[l, r]~ có bao nhiêu số đặc biệt.

Yêu cầu: với mỗi cặp số nguyên ~l, r~ (~1 \le l \le r \le 10^{18}~), xác định số lượng số đặc biệt nằm trong đoạn ~[l, r]~.

Dữ liệu

• Dòng đầu chứa số nguyên dương ~t~ là số lượng đoạn cần xác định số lượng số đặc biệt;
• ~t~ dòng tiếp theo, mỗi dòng chứa hai số ~l, r~.

Kết quả

Gồm ~t~ dòng, mỗi dòng chứa một số nguyên là kết quả tìm được tương ứng.

Ví dụ

PEARL.INP

1
2941999 2942002

PEARL.OUT

1

Giới hạn

• Có 20% số test có ~t \le 30~ và ~r - l \le 10^6~.
• Có 20% số test có ~t \le 100~; ~1 \le l \le r \le 10^9~.
• Có 60% số test có ~t \le 100~; ~1 \le l \le r \le 10^{18}~.