# Lời giải bài Tam Giác Nguyên Tố
# Tóm tắt đề
Cho một tam giác nguyên tố chứa tất cả các số nguyên tố, với mỗi số tìm vị trí của số đó trong tam giác nguyên tố.
### Subtask:
- Subtask1: $x$ $\leq 10^4$
- Subtask2: $x$ $\leq 10^7$
# Subtask 1: $x$ $\leq 10^4$
- Dùng hàm kiểm tra nguyên tố và một chút tính chất để tìm vị trí. Với mỗi tầng của tam giác tương ứng với dãy tịnh tiến từ 1, 2, 3, 4,....Do đó ta dùng một mảng vector để lưu số lượng số nguyên tố tương ứng với mỗi tầng. Với mỗi truy vấn, ta sẽ chặt nhị phân để xem số đó thuộc tầng nào và kết hợp với một chút toán.
- Đpt: $sqrt(x)*T$.

bool snt(int n){
	if (n < 2) return false;
	for (int i = 2; i <= sqrt(n); i++)
		if (n % i == 0)
			return false;
	return true;
}
void sub1(){
    int t=1;
    cin >> t;
    for(int i=2; i<N; ++i)
    {
        if(snt(i) == true)
            g[i]=++k;
    }
    int j=0,val=1;
    while(j<=N)
    {
        j+=val;
        ++val;
        res1.emb(j);
    }
    while(t--)
    {
        cin >> n;
        if(!c[n])
        {
            cout<<-1;
        }
        else
        {
            int u=g[n];
            int v=lower_bound(res1.begin(),res1.end(),u)-res1.begin()-1;
            if(n==2)
            {
                cout <<1<<" "<<1;
            }
            else
                cout <<v+2<<" "<<u-res1[v];
        }
        cout<<'\n';
    }
}

# Subtask 2: $x$ $\leq 10^7$
- Ta sử dùng sàng nguyên tố để có thể kiểm tra $1$ số có phải là số nguyên tố không trong $O(1)$. Phần còn lại xử lý giống Subtask $1$
- Đpt: $O(T)$

void sub2(){
    int t=1;
    cin >> t;
    for(int i=2; i<N; ++i)c[i]=true;
    for(int i=2; i<N; ++i)
    {
        if(c[i])
        {
            for(int j=i*2; j<N; j+=i)c[j]=false;
            g[i]=++k;;
        }
    }
    int j=0,val=1;
    while(j<=N)
    {
        j+=val;
        ++val;
        res1.emb(j);
    }
    while(t--)
    {
        cin >> n;
        if(!c[n])
        {
            cout<<-1;
        }
        else
        {
            int u=g[n];
            int v=lower_bound(res1.begin(),res1.end(),u)-res1.begin()-1;
            if(n==2)
            {
                cout <<1<<" "<<1;
            }
            else
                cout <<v+2<<" "<<u-res1[v];
        }
        cout<<'\n';
    }
}