Problem Description

Tina Town is a friendly place. People there care about each other.

Tina has a ball called zball. Zball is magic. It grows larger every day. On the first day, it becomes  time as large as its original size. On the second day,it will become  times as large as the size on the first day. On the n-th day,it will become n times as large as the size on the (n-)-th day. Tina want to know its size on the (n-)-th day modulo n.

Input

The first line of input contains an integer T, representing the number of cases.

The following T lines, each line contains an integer n, according to the description.

T≤,≤n≤

Output

For each test case, output an integer representing the answer.

Sample Input

Sample Output

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <stack>

#include <math.h>

#include <queue>

#include <vector>

using namespace std;

#define N 10010

#define ll long long

#define met(a,b) memset(a,b,sizeof(a));

vector<vector<int> >Q;

int n;

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int f=;

        scanf("%d",&n);

        if(n==)///特例

        {

            printf("2\n");

            continue;

        }

        int k=(int)sqrt(n);

        for(int i=; i<=k; i++)

        {

            if(n%i==)

            {

                f=;

                break;

            }

        }

        if(f)

            printf("0\n");

        else

            printf("%d\n",n-);

    }

    return ;

}