#include <cstdint>
#include <iostream>
#include <map>
#include <numeric>
#include <utility>
#include <vector>

using i64 = std::int64_t;

std::vector<int> make_primes() {
    constexpr int limit = 31623;
    std::vector<bool> composite(limit + 1, false);
    std::vector<int> primes;
    for (int i = 2; i <= limit; ++i) {
        if (composite[i]) continue;
        primes.push_back(i);
        if (i64{i} * i <= limit) {
            for (int j = i * i; j <= limit; j += i) composite[j] = true;
        }
    }
    return primes;
}

std::vector<std::pair<i64, int>> factor(i64 x, const std::vector<int>& primes) {
    std::vector<std::pair<i64, int>> result;
    for (int p : primes) {
        if (i64{p} * p > x) break;
        if (x % p != 0) continue;
        int exponent = 0;
        do {
            x /= p;
            ++exponent;
        } while (x % p == 0);
        result.emplace_back(p, exponent);
    }
    if (x > 1) result.emplace_back(x, 1);
    return result;
}

i64 solve(i64 n, const std::vector<int>& primes) {
    if (n == 1) return 1;

    // freq[q][b] counts cyclic factors C_(q^b), with b >= 1.
    std::map<i64, std::vector<int>> freq;
    const auto add_cycle = [&](i64 length) {
        for (auto [q, b] : factor(length, primes)) {
            auto& counts = freq[q];
            if (static_cast<int>(counts.size()) <= b) counts.resize(b + 1, 0);
            ++counts[b];
        }
    };

    for (auto [p, e] : factor(n, primes)) {
        if (p == 2) {
            if (e >= 2) add_cycle(2);
            if (e >= 3) add_cycle(i64{1} << (e - 2));
        } else {
            i64 length = p - 1;
            for (int j = 1; j < e; ++j) length *= p;
            add_cycle(length);
        }
    }

    i64 answer = 1;
    for (const auto& [q, counts] : freq) {
        int active = std::accumulate(counts.begin(), counts.end(), 0);
        i64 previous = 1;
        i64 order = 1;
        i64 subtotal = 1;
        for (int k = 1; k < static_cast<int>(counts.size()); ++k) {
            order *= q;
            i64 current = previous;
            // F(k) / F(k-1) = q^(number of factors with exponent >= k).
            for (int j = 0; j < active; ++j) current *= q;
            subtotal += order * (current - previous);
            previous = current;
            active -= counts[k];
        }
        answer *= subtotal;
    }
    return answer;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    const auto primes = make_primes();
    int t;
    if (!(std::cin >> t)) return 0;
    while (t--) {
        i64 n;
        std::cin >> n;
        std::cout << solve(n, primes) << '\n';
    }
}