#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
bool helper(const vector<int>& serverLoad, int maxOperations, int K) {
    vector<int> loads = serverLoad;
    int n = loads.size();

    for (int op = 0; op < maxOperations; ++op) {
        if (loads.empty()) return true; 
        int maxLoad = *max_element(loads.begin(), loads.end());
        int threshold = maxLoad / 2;
        vector<int> newLoads;
        for (int load : loads) {
            if (load <= threshold) {
                newLoads.push_back(load);
            }
        }

        loads = newLoads;
    }
    return loads.size() <= K;
}

int getMinToolRuns(const vector<int>& serverLoad, int K) {
    int left = 0;
    int right = serverLoad.size();

    int result = right;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (helper(serverLoad, mid, K)) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return result;
}

#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int MOD = 1000000007;
int solve(const string& s2, int n, int x, int y) {
    int s_length = s2.length();
    vector<char> s(s_length);
        for (int i = 0; i < s_length; i++) {
        s[i] = s2[i];
    }
    
    vector<int> prevSame(s_length, -1);
    int idxL = -1;
    int idxR = -1;
    
    for (int i = 0; i < s_length; i++) {
        if (s[i] == 'l') {
            prevSame[i] = idxL;
            idxL = i;
        } else {
            prevSame[i] = idxR;
            idxR = i;
        }
    }

    vector<vector<long>> dp(s_length + 1, vector<long>(n + 1, 0));
    dp[0][x] = 1;
    
    for (int i = 1; i <= s_length; i++) {
        for (int j = 0; j <= n; j++) {
            dp[i][j] = dp[i - 1][j];
            if (s[i - 1] == 'l') {
                if (j + 1 <= n) dp[i][j] += dp[i - 1][j + 1];
                if (j + 1 <= n && prevSame[i - 1] >= 0) dp[i][j] -= dp[prevSame[i - 1] + 1 - 1][j + 1];
            } else {
                if (j - 1 >= 0) dp[i][j] += dp[i - 1][j - 1];
                if (j - 1 >= 0 && prevSame[i - 1] >= 0) dp[i][j] -= dp[prevSame[i - 1] + 1 - 1][j - 1];
            }
            dp[i][j] = (dp[i][j] + MOD) % MOD;
        }
    }
    
    return static_cast<int>(dp[s_length][y]);
}

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    int maxA = *max_element(A.begin(), A.end());
    vector<long long> dp(maxA + 1, 0);
    vector<long long> count(maxA + 1, 0);

    for (int i = 0; i < N; i++) {
        count[A[i]]++;
    }
    for (int g = maxA; g >= 1; g--) {
        long long cnt = 0;
        for (int mul = g; mul <= maxA; mul += g) {
            cnt = (cnt + dp[mul]) % MOD;
        }
        cnt = (cnt + (1LL << count[g]) - 1) % MOD;
        dp[g] = cnt;
    }

    for (int i = 0; i < N; i++) {
        cout << dp[A[i]] << " ";
    }
    cout << endl;

    return 0;
}

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<int> solve(int T, vector<long long>& test_cases) {
    vector<int> results;
    results.reserve(T);
    
    for (const auto& N : test_cases) {
        results.push_back(static_cast<int>(sqrt(N)));
    }
    
    return results;
}

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> findMatrix(const vector<vector<int>>& a) {
    int n = a.size();
    int m = a[0].size();
        vector<vector<int>> prefix(n, vector<int>(m, 0));
    vector<vector<int>> b(n, vector<int>(m, 0));
        for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            prefix[i][j] = a[i][j];
            if (i > 0) prefix[i][j] += prefix[i-1][j];
            if (j > 0) prefix[i][j] += prefix[i][j-1];
            if (i > 0 && j > 0) prefix[i][j] -= prefix[i-1][j-1];
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            b[i][j] = prefix[i][j];
        }
    }
    
    return b;
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
pair<ll,ll>bfs(ll n,ll u,vector<ll>adj[])
{
    ll dis[n];
    memset(dis,-1,sizeof(dis));
    queue<ll>q;
    q.push(u);
    dis[u] = 0;
    while (!q.empty()) {
        ll t = q.front();
        q.pop();
        for (auto v:adj[t]) 
        {
            if (dis[v] == -1) 
            {
                q.push(v);
                dis[v]=dis[t]+1;
            }
        }
    }
    ll maxi=0;
    ll ind;
    for (ll i=0;i<n;i++) 
    {
        if (dis[i]>maxi) 
        {
            maxi=dis[i];
            ind=i;
        }
    }
    return {ind, maxi};

}
ll solve(ll n,vector<ll>&from,vector<ll>&to)
{   
    vector<ll>adj[n];
    for(ll i=0;i<from.size();i++)
    {
        adj[from[i]-1].push_back(to[i]-1);    
        adj[to[i]-1].push_back(from[i]-1); 
    }
    pair<ll,ll>t1,t2;
    t1=bfs(n,0,adj);
    t2=bfs(n,t1.first,adj);
    return t2.second;
}
signed main()
{
    ll n,q; cin>>n>>q;
    vector<ll>from(q),to(q);
    for(ll i=0;i<q;i++) cin>>from[i];
    for(ll i=0;i<q;i++) cin>>to[i];
    cout<<solve(n,from,to);
}   

#define int long long
int countValidKs(int s) {
    int count = 0;
    for (int n = 1; n * (n - 1) / 2 < s; n++) {
        int num = s - (n * (n - 1)) / 2;
        if (num > 0 && num % n == 0) {
            count++;
        }
    }
    return count;
}

def findPodCount(n, pods, logs):
    for start, end, x in logs:
        for i in range(start - 1, end):
            pods[i] = max(pods[i], x)
    
    min_pods = min(pods)
    return [max(pod, min_pods) for pod in pods]