Gigel, mare amator de probleme de matematică şi informatică, a observat că unele numere prime au o proprietate interesantă: orice cifră ar elimina dintr-un astfel de număr, numărul obţinut este tot număr prim. A numit astfel de numere numere extraprime. De exemplu, numărul 317 este un număr extraprim: el este număr prim şi, în plus, dacă eliminăm cifra 3, obţinem 17, care este prim; dacă eliminăm 1, obţinem 37, care este prim; dacă eliminăm 7, obţinem 31, care este şi el număr prim.

Cerință

Spunem că x este între a şi b dacă x≥a şi x≤b. Fiind date două valori naturale a şi b, să se determine câte numere extraprime există între a şi b, precum şi cel mai mic şi cel mai mare număr extraprim dintre a şi b.

Date de intrare

Fișierul de intrare extraprime.in conține pe prima linie cele două valori naturale a şi b, separate printr-un spaţiu.

Date de ieșire

Fișierul de ieșire extraprime.out va conține 3 linii. Pe prima linie se va scrie un număr natural nr reprezentând numărul de numere extraprime dintre a şi b. Pe linia a doua a fişierului de ieşire se va scrie cel mai mic număr extraprim dintre a şi b, iar pe linia a treia a fişierului de ieşire se va scrie cel mai mare număr extraprim dintre a şi b.

Restricții și precizări

• 10 < a ≤ b < 10000000;
• Numărul 1 nu este prim;
• Pentru datele de test există întotdeauna soluţie;

Exemplu

extraprime.in

10 100

extraprime.out

4
23
73

Explicație

Se află 4 numere extraprime mai mari decât 10 şi mai mici decât 100: 23, 37, 53 şi 73.

#include <bits/stdc++.h>
using namespace std;
ifstream cin("extraprime.in");
ofstream cout("extraprime.out");
bool ciur[10000005];
int a , b , cif[10] , ncif;
void Ciur()
{
    ciur[1] = 1;
    for(int i = 4 ; i <= 10000000; i += 2) ciur[i] = 1;
    for(int i = 3; i * i <= 10000000; i += 2)
        if(!(ciur[i]))
            for(int j = i * i ; j <= 10000000; j += 2 * i)
                ciur[j] = 1;

}
int extra(int x)
{
    ncif=0;
    if(ciur[x]) return false;
    while(x)
    {
        cif[++ncif]=x%10;
        x/=10;
    }
    for(int i = ncif ; i >= 1 ; i--)
    {
        int x = 0;
        for(int j = ncif ; j >= 1 ; j--)
            if(i!=j) x = x * 10 + cif[j];
        if(ciur[x]) return false;
    }
    return true;
}
int main()
{
    int s = 0;
    Ciur();
    cin >> a >> b;
    int maxim = -1000000000 , minim = 1000000000;
    for(int i = a ; i <= b ; i++)
    {
        int nr = i;
        if(extra(nr))
        {
            maxim=max(maxim , nr);
            s++;
            minim=min(minim , nr);
        }
    }
    cout<<s<<'\n' << minim << '\n' << maxim;
    return 0;
}