Ultra Weak Goldbach's Conjecture

In number theory, Goldbach's conjecture states that every even integer greater than $$$2$$$ is the sum of two prime numbers. A weaker version of this conjecture states that every odd number greater than $$$5$$$ is the sum of three prime numbers.

Here is an ultra weak version of Goldbach's conjecture: every integer greater than $$$11$$$ is the sum of $$$\textbf{six}$$$ prime numbers. Can you help to verify or disprove this conjecture?

Input

The first line of the input gives the number of test cases, $$$T$$$ ($$$1 \le T \le 200$$$). $$$T$$$ test cases follow.

Each test case contains one integer $$$N$$$ ($$$1 \le N \le 10^{12}$$$).

Output

For each test case, output "Case x:" first, where x is the test case number (starting from $$$1$$$). If the solution exist, output six prime numbers separated by spaces; otherwise output "IMPOSSIBLE" (quotes for clarity) when the solution does not exist. When the solution exists, any valid solution is acceptable.

Sample Input

Input

5
6
13
200
570
680

Output

Case 1: IMPOSSIBLE
Case 2: 2 2 2 2 2 3
Case 3: 43 29 31 29 31 37
Case 4: 97 101 103 107 101 61
Case 5: 137 137 107 113 89 97

题意：给你一个数，让你把它拆成六个素数和

思路：对于一个奇数p，我们可以在[p-300,p)的范围内找一个素数q，然后得到x=p-q；因为x<=300,直接爆力判断就好了。所以

如果n是奇数，我们把它拆去三个2，然后拆分，n是偶数，如果n%4==0，把n先拆成n/2-1,n/2+1,否则拆成两个n/2,然后拆分

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;//根据需要改成unsigned long long

const int times=20; int num=0;
ll ans[10];
ll mul(ll x,ll y,ll MOD){
    x=x%MOD,y=y%MOD;
    return ((x*y-(ll)(((long double)x*y+0.5)/MOD)*MOD)%MOD+MOD)%MOD;
}

ll Random(ll n){
    return ((double)rand()/RAND_MAX*n+0.5);
}

ll pw(ll a,ll b,ll MOD){
    ll ans=1;
    while(b){
        if(b&1) ans=mul(ans,a,MOD);
        b/=2;
        a=mul(a,a,MOD);
    }
    return ans;
}

bool witness(ll a,ll n){
    ll tmp=n-1;
    int j=0;
    while(tmp%2==0){
        tmp/=2;
        ++j;
    }
    ll x=pw(a,tmp,n);
    if(x==1 || x==n-1) return true;
    while(j--){
        x=mul(x,x,n);
        if(x==n-1) return true;
    }
    return false;
}

bool miller(ll n){
    if(n==2) return true;
    if(n<2 || n%2==0) return false;
    for(int i=1;i<=times;++i){
        ll a=Random(n-2)+1;
        if(!witness(a,n)) return false;
    }
    return true;
}
void js(ll n)
{
    for(ll i=2;i<=n/2;i++)
    {
        if(miller(i)&&miller(n-i))
        {
            ans[++num]=i;
            ans[++num]=n-i;
            break;
        }
    }
}
void getans(ll n){
    if(n>=400)
    {
        for(ll i=n-400;i<=n;i++){
        if(i%2==1&&miller(i)==1){
            ans[++num]=i;
            js(n-i);
            break;
        }
        //printf("0000\n");
    }
    }
    else
    {
        ans[++num]=3;
        n-=3;
        js(n);
    }
}
int main(){
    int t;
    scanf("%d",&t);
    int cas=0;
    while(t--){
        ll n;
        scanf("%lld",&n);
        printf("Case %d: ",++cas);
        if(n<=11)
        {
            printf("IMPOSSIBLE\n");
            continue;
        }
        else if(n==12)
        {
            printf("2 2 2 2 2 2\n");
            continue;
        }
       num=0;
        if(n%2==1){
            ans[++num]=2;
            ans[++num]=2;
            ans[++num]=2;
            getans(n-6);
        }
        else{
            if(n%4==0){
                getans(n/2-1);
                getans(n/2+1);
            }
            else{
                getans(n/2);
                getans(n/2);
            }
        }

        for(int i=1;i<=6;i++)
        {
            if(i==6)
            {
                printf("%lld\n",ans[i]);
                break;
            }
            printf("%lld ",ans[i]);
        }
    }
}