Q10533: Digit Primes

質數（prime）為一個正數，且除了1與本身之外沒有其他的因數。一個digit prime是一個質數，且其中的每個數的和也是質數。例如：41 是一個digit prime，因為 4+1=5，而 5 也是一個質數。17 就不是一個digit prime，因為 1+7=8，而 8 並不是質數。你的任務是找出一定的範圍內有多少個 digit prime。

Input

輸入的第一列有一個整數N（0 < N <= 500000）代表以下有多少組測試資料。

每組測試資料一列。含有2個整數 t1、t2（0 < t1 <= t2 < 1000000）。

Output

對每組測試資料輸出一列，介於 t1 和 t2 之間（包含 t1 t2）有多少個 digit prime。