#include<vector>
using namespace std;
int main()
{
    int t;
    cin >> t;
    int N;
    for (int i = 0;i<t;++i)
    {
        vector<int>num;
        int Result = 0;
        cin >> N;
        for (int i = 0;i < A;++i)
        {
            num.push_back(0);
        if (N == 0)
        {
            Result = 0;
        }
        else if (N == 1)
        {
            Result = 2;
        }
        else if (N == 3)
        {
            Result = 3;
        }
        else
        {
            for (int i = 1;i < sum + 1;++i)
            {
                int x = ((N + 1)*i) % sum;
                if (num[x] == 1)
                {
                    Result++;
                    break;
                }
                else if (num[x] == 0)
                {
                    num[x] = 1;
                    Result++;
                }
            }

        }
        cout << Result << endl;
    }
}