讓我們定義dn為：dn=pn+1?pn，其中pi是第i個素數(shù)。顯然有d1=1，且對于n>1有dn是偶數(shù)。“素數(shù)對猜想”認(rèn)為“存在無窮多對相鄰且差為2的素數(shù)”。

現(xiàn)給定任意正整數(shù)N(<105)，請計算不超過N的滿足猜想的素數(shù)對的個數(shù)。

輸入格式:

輸入在一行給出正整數(shù)N。

輸出格式:

在一行中輸出不超過N的滿足猜想的素數(shù)對的個數(shù)。

輸入樣例:

20


輸出樣例:

4

普通的素數(shù)判定會在最后一組t掉，考慮使用素數(shù)篩。這里給出常用兩種篩的模板。
（1）埃氏篩：

（2）歐拉篩：