Sophie

Cerință

Un număr $i$ este numit număr Sophie Germain dacă $i$ este prim și $2 \cdot i + 1$ este, de asemenea, prim.
Se poate generaliza acest concept astfel: $i$ este considerat număr $k$-Sophie Germain dacă $i$ este prim și $i \cdot k+1$ este, de asemenea, prim, pentru un număr $k$ natural nenul, $k \gt 2$.

1. Dându-se un număr natural nenul $n$, să se calculeze câte numere Sophie Germain există între $1$ și $n$.
2. Dându-se două numere naturale nenule $n$ și $k$, să se calculeze câte numere $k$-Sophie Germain există între $1$ si $n$.

Date de intrare

Pe prima linie a fișierului de intrare sophie.in se găsește un număr natural $c$, care poate să fie doar $1$ sau $2$, reprezentând numărul cerinței de rezolvat.

Dacă cerința este $c=1$, pe a doua linie se găsește un număr natural nenul $n$, cu semnificația din enunț.
Dacă cerința este $c=2$, pe a doua linie se găsesc două numere naturale nenule $n$ și $k$, separate printr-un spațiu, cu semnificația din enunț.

Date de ieșire

În fișierul sophie.out se va afișa un număr natural care reprezintă numărul cerut.

Restricții și precizări

• $1 \leq n, k \leq 10^6$;
• Pentru prima cerință ($c=1$) se acordă $40$ puncte.
• Pentru a doua cerință ($c=2$) se acordă $60$ puncte. Dintre acestea, pentru $15$ puncte, $k$ este impar. Pentru alte $15$ puncte, $n \cdot k \leq 10^6$.

Exemplul 1

sophie.in

1
10

sophie.out

3

Explicație

Cerința este 1.
Numerele Sophie Germain între $1$ și $10$ sunt:

• $2$: $2$ este prim, iar $2 \cdot 2+1=5$ și $5$ este prim.
• $3$: $3$ este prim, $3 \cdot 2+1=7$, iar $7$ este prim.
• $5$: $5$ este prim, iar $5 \cdot 2 + 1 = 11$, unde $11$ este prim.

Exemplul 2

sophie.in

2
10 20

sophie.out

3

Explicație

Cerința este 2.
Singurele numere care respectă condiția între $1$ și $10$ sunt:

• $2$ ($2$ este prim și $2 \cdot 20+1=41$ este prim);
• $3$ ($3$ este prim și $61$ este număr prim);
• $5$ ($5$ este prim și $101$ este număr prim).