Cerința

Se dau n numere naturale. Pentru fiecare număr k dat, să se afle cea mai lungă secvenţă de numere naturale consecutive din şirul 1,2,3,...,k, astfel încât orice număr din secvenţă să nu fie prim.

Date de intrare

Fișierul de intrare prim997.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire prim997.out va conține pe linia i, primul număr din secvenţă şi lungimea secvenţei, pentru cel de-al i-lea număr de pe linia a doua a fişierului de intrare.

Restricții și precizări

• 1 ≤ n ≤ 100.000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 10.000.000
• dacă sunt mai multe secvenţe de lungime maximă cu numere consecutive neprime, se va afişa cea cu primul număr din secvenţă minim

Exemplu

prim997.in

3
4 11 30

prim997.out

1 1
8 3
24 5

Explicație

În şirul 1,2,3,4 secvenţa de lungime maximă cu numere neprime este 1, în şirul 1,2,3,4,5,6,7,8,9,10,11 secvenţa este 8,9,10, iar în şirul 1,2,3,4,...,30 este 24,25,26,27,28.

#include <bits/stdc++.h>
using namespace std;
ifstream cin("prim997.in");
ofstream cout("prim997.out");
int st[10001001] , l[10001101] ;
bool a[10001001];
int n;

int main()
{
    int max=10001001;
    for(int i = 2 ; i <= max ; i++) a[i] = 1;
    for(int i = 2 ; i*i <= max ; i++)
        if(a[i] == 1)
            for(int j = i*i; j <= max; j += i) a[j]=0;
    int lun = 0 , lmax=0;
    for(int i = 1 ; i <= 10000000 ; ++i)
    {
        l[i]=l[i-1] , st[i]=st[i-1];
        if(a[i]==0)
        {
            lun++;
            if(lun>lmax)
                lmax=lun , l[i]=lmax , st[i]=i-lmax+1;
        }
        if(a[i]==1)
            lun=0;
    }
    cin >> n;
    for(int i = 0 ; i < n ; ++i)
    {
        int x;
        cin >> x;
        cout << st[x] << ' ' << l[x] << endl;
    }
    return 0;
}