Một số được coi là thuần nguyên tố nếu nó là số nguyên tố, tất cả các chữ số là số nguyên tố và tổng các chữ số của nó cũng là số nguyên tố. Bài toán đặt ra là đếm trong một đoạn giữa hai số nguyên cho trước có bao nhiêu số thuần nguyên tố?

Input

• Dòng đầu tiên nhập số nguyên dương \(T\) là số bộ test (\(1 \leq T \leq 20\)).
• \(T\) dòng tiếp theo mỗi dòng nhập 2 số nguyên dương \(A, B\) (\(1 \leq A \leq B \leq 10^6\)).

Output

• Mỗi testcase in ra kết quả theo yêu cầu đề bài.

Example

2
23 199
2345 6789

1
15