Một số được gọi là "May Mắn" nếu tổng các chữ số của nó là một số nguyên tố.
Tuy nhiên, có một ngoại lệ: Nếu số đó chứa chữ số '4', nó sẽ bị coi là "Xui Xẻo" bất kể tổng chữ số là gì.

Cho số nguyên dương \(T\) là số lượng truy vấn, với mỗi truy vấn nhập vào:

• \(2\) số nguyên dương \(A\) và \(B\) \((1 ≤ A < B ≤ 10^6)\)

Yêu cầu: Hãy tính xem trong đoạn [A, B] có bao nhiêu só may mắn.

Input:

• Dòng đầu tiên chứa một số nguyên dương T là số truy vấn
• T dòng tiếp theo chứa 2 số nguyên dương A, B.

Output:

• T dòng tương ứng với kết quả cho từng truy vấn.

Example

2
1 10
1 4 

4
2

Scoring

• Subtask 1 (\(20\%\) điểm): \(T = 1, B \le 100\).
• Subtask 2 (\(30\%\) điểm): \(T \le 100, B \le 2000\).
• Subtask 3 (\(50\%\) điểm): \(T \le 10^5, B \le 10^6\).