d438: 10533 - Digit Primes
Tags :
Accepted rate : 190人/236人 ( 81% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-04-04 18:23

Content

質數(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

Sample Input
3
10 20
10 100
100 10000
Sample Output
1
10
576 
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 3.0s , <10M
Hint :
Tags:
出處:
UVa10533 [管理者:
morris1028 (碼畜)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」