Lại là số nguyên tố

Bạn có thể biểu diễn 1 số thành tổng của một số số nguyên tố liên tiếp. Ví dụ, số 15 có thể biều diễn thành 3+5+7=15.

Cho số nguyên dương n (1≤n≤100 000) và bạn phải tìm số cách khác nhau biểu diễn n thành tổng các số nguyên tố liên tiếp.

Input

Dòng đầu là số bộ test. Các dòng sau, mỗi dòng một bộ test gồm một số nguyên dương n .

Output

Với mỗi bộ test, in ra trên một dòng số cách biểu diễn n thành tổng các số nguyên tố liên tiếp.

Sample Input	Sample Output
2 3 17	1  2

#include<iostream>
#include<math.h>


long n;

int test_nguyen_to( long k)
{
     int t = (int)sqrt(k);
     for(int i = 3;i<= t ;i+=2)
     if(k%i == 0)return 0;
     return 1;
}

int test_danh_sach_nguyen_to(int a[])
{
     
     a[1] =2;
     int k=1, dem =0;
     for( long i =3;i<n;i+=2)
     {
          if (test_nguyen_to(i)) a[++k] = i;
          if( a[k] + a[k-1] >= n)break;
     }
     
     
     if(n%2 &&test_nguyen_to(n)) dem = 1;
     
     int i =1,j;
     long sum ;
     do{
          j = i;
          sum = 0;
         
         do{
                   sum +=a[j];
                   ++j;
           }while(sum <n && j<=k);
         
         if(sum == n) ++dem;
         
         ++i;
         } while( i <=k);
         
         
     return dem;
}

int main()
{
    int slg;
    std::cin>>slg;
    for( int i =1;i<=slg;++i)
    {
    std::cin>>n;
    int a[n];
    std::cout<< test_danh_sach_nguyen_to(a)<< std::endl;
    }
  //  system("pause");
    return 0;
}