“红旗杯”第十五届黑龙江省大学生程序设计竞赛——Goodbye

Problem Description

“Goodbye to the friends I’ve had, goodbye to my upstairs neighbor, goodbye to the kids downstairs, and anybody who lend me a favor.”

“Or, goodbye to the positive proper divisor?”

That game is popular these days. Two player take turns to choose a specific number and claim it. The player who takes the first turn chooses one positive proper divisor of given n. In the next rounds, player should choose one positive proper divisor (真因数) of the number claimed in the previous round. The player who can’t make a choice will win.

Formally, a positive proper divisor of n is a divisor of n, and it cannot be either 1 or n.

Now Chino is going to play this game with David. Chino always wants to win and meanwhile she wants to keep the chosen number as big as possible. If with the given n, Chino will win directly or fail anyway, you should also tell her.

Can you help Chino to choose her answer in the first round?

Input

The first line contains one integer T (1 ≤ T ≤ $10^3$) denoting the count of testcases.

For each testcase, one line with one integer n (1 ≤ n ≤ $10^5$) denoting the given n in one game.

Output

For each testcase, you should output the biggest choice, or 0 when Chino will win directly, or -1 when Chino will fail anyway.

Sample Input

4 3 4 8 666

Sample Output

0 -1 4 111

Code

#include <iostream>
#include <vector>

using namespace std;

const int maxn = 100010;

int prime[maxn]; bool is_prime[maxn];
vector<int> prime_tmp[maxn];

int sieve(int n)
{
    int p = 0;
    for(int i = 0; i <= n; ++i)
        is_prime[i] = true;
    is_prime[0] = is_prime[1] = false;
    for(int i = 2; i <= n; ++i)
    {
        if(is_prime[i])
        {
            prime[p++] = i;
            for(int j = i + i; j <= n; j += i)
            {
                is_prime[j]=false;
                prime_tmp[j].push_back(i);
                prime_tmp[j].push_back(j / i);
            }    
        }
    }
    
    return p;
}

int solve(int n)
{
    int ans = -1;
    for(int i = 0; i < prime_tmp[n].size(); i++)
    {
        int tmp = prime_tmp[n][i];
        if(!is_prime[tmp] && tmp > ans)
        {
            int pd = solve(tmp);
            
            if(pd == -1)
                ans = tmp;
            else{
                if(pd > ans)
                    ans = pd;
            }
        }
    }
    
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    sieve(100000);
    
    int t;
    cin>>t;

    while(t--)
    {
        int n;
        cin>>n;

        if(n == 1 || is_prime[n])
            cout<<0<<endl;
        else{
            int ans = solve(n);
            cout<<ans<<endl; 
        }
    }
    return 0;
}