// Arup Guha
// 10/12/2023
// Slow Solution to CIS 3362 Homework #5 Question #9 (for half credit.)

using namespace std;

#include <iostream>
#include <vector>

int phi(int n);
long long sum(int n);

int main() {

    int nC;
    cin >> nC;

    // Process cases.
    for (int loop=0; loop<nC; loop++) {
        long long p;
        cin >> p;

        long long res = 0;

        // b is the base we are exponentiating.
        for (int b=1; b<p; b++) {

            long long tmp = b;
            int add = 1;

            // Keep exponentiating until we reach 1.
            while (tmp != 1) {
                tmp = (tmp*b)%p;
                add++;
            }

            // Add to running tally.
            res += add;
        }

        // Ta da!
        cout << res << endl;
    }

    return 0;
}