Siêu nguyên tố

Một số nguyên tố \(a\) được gọi là siêu nguyên tố nếu khi lần lượt xoá đi một hoặc nhiều chữ số ở bên phải của \(a\), mọi số nhận được đều là số nguyên tố.

Ví dụ: \(2, 3, 5, 7\) là siêu nguyên tố. \(2399\) là siêu nguyên tố vì \(239\), \(23\) và \(2\) đều là số nguyên tố. Còn \(19\) không phải siêu nguyên tố vì xoá chữ số cuối được \(1\), không phải số nguyên tố.

Cho \(N\) đoạn \([u, v]\). Với mỗi đoạn, hãy đếm có bao nhiêu số siêu nguyên tố thuộc đoạn đó (kể cả hai đầu mút).

Input

• Dòng đầu: số nguyên dương \(N\).
• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\).

Output

In ra \(N\) dòng, dòng thứ \(i\) là số lượng siêu nguyên tố trong đoạn thứ \(i\).

Constraints

• \(1 \le N \le 50000\).
• \(1 \le u \le v \le 10^{23}\) (các số có thể vượt quá phạm vi số nguyên 64 bit, hãy đọc dưới dạng xâu).
• Subtask: 30% số test có \(u, v \le 200\); 30% số test có \(u, v \le 2000\); 20% số test có \(v \le 10^9\); 20% số test còn lại có \(v \le 10^{23}\).

Sample Input

3
1 100
20 25
30 800

Sample Output

13
1
21

Explanation

Trong \([1,100]\) có \(13\) số: \(2, 3, 5, 7, 23, 29, 31, 37, 53, 59, 71, 73, 79\). Trong \([20,25]\) chỉ có \(23\).