#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()

#define int int64_t

int get2(int z, int k) {
    z %= (1ll << k);
    if (k == 0) return 1;
    if (k == 1) return 2;
    if (k == 2) {
        if (z == 0) return 4;
        if (z == 1) return 8;
        if (z == 2) return 4;
        return 0;
    }
    if (z % 4 == 0) {
        return get2(z / 4, k - 2) * 4;
    }
    if (z % 8 == 2 || z % 8 == 1 || z % 8 == 5) {
        return (1ll << (k + 1));
    }
    return 0;
}

int getp(int z, int p) {
    z %= p;
    int x = -1;
    int res = 1;
    int n = (p - 1) / 2;
    while (n) {
        if (n % 2 == 0) {
            x *= x;
            n /= 2;
        } else {
            res *= x;
            n--;
        }
    }
    if (z == 0) {
        if (res == 1) {
            return 2 * p - 1;
        } else {
            return 1;
        }
    }
    return p - res;
}

int getpa(int z, int p, int a) {
    if (a == 0) {
        return 1;
    }
    if (z % p != 0) {
        int res = getp(z, p);
        for (int i = 1; i < a; ++i) {
            res *= p;
        }
        return res;
    }
    int res = getp(0, p) - 1;
    for (int i = 1; i < a; ++i) {
        res *= p;
    }
    if (a == 1) {
        ++res;
        return res;
    }
    if (z % (p * p) == 0) {
        res += getpa(z / p / p, p, a - 2) * p * p;
        return res;
    }
    return res;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
        int m, n;
        cin >> m >> n;
        for (int i = 0; i < n; ++i) {
            int z;
            cin >> z;
            /// z = i;
            int ans = 1;
            int m1 = m;
            int k = 0;
            while (m % 2 == 0) {
                m /= 2;
                ++k;
            }
            ans *= get2(z, k);
            for (int p = 3; p * p <= m; ++p) {
                if (m % p == 0) {
                    int a = 0;
                    while (m % p == 0) {
                        m /= p;
                        ++a;
                    }
                    ans *= getpa(z, p, a);
                }
            }
            if (m != 1) {
                ans *= getp(z, m);
            }
            m = m1;
            cout << ans << " ";
        }
        cout << "\n";
    return 0;
}