#define N 1000000
int fac[1000005][3];
int g[1005][1005];
int prime[N];
bool vis[N];
int cnt = 1;
ll a[5005];
ll b[5005];

void init() {
    fac[1][1] = fac[1][0] = fac[1][2] = 1;
    for (int i = 2;i <= N;i++) {
        if (!vis[i]) {
            prime[cnt++] = i;
            fac[i][0] = i;
            fac[i][1] = 1;
            fac[i][2] = 1;
        }
        for (int j = 1;j < cnt;j++) {
            if (i * prime[j] > N)break;
            vis[i * prime[j]] = true;
            fac[i * prime[j]][0] = fac[i][0] * prime[j];
            fac[i * prime[j]][1] = fac[i][1];
            fac[i * prime[j]][2] = fac[i][2];
            sort(fac[i * prime[j]], fac[i * prime[j]] + 3);
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
    for (int i = 1;i <= 1000;i++) {
        g[i][0] = g[0][i] = i;
        for (int j = 1;j <= i;j++) {
            g[i][j] = g[j][i] = g[j][i % j];
        }
    }
}


ll getgcd(int x, int y) {
    if (x == 1 || y == 1)return 1;
    int a = (fac[x][0] <= 1000) ? g[fac[x][0]][y % fac[x][0]] : (y % fac[x][0] == 0) ? fac[x][0] : 1;
    y = y / a;
    int b = (fac[x][1] <= 1000) ? g[fac[x][1]][y % fac[x][1]] : (y % fac[x][1] == 0) ? fac[x][1] : 1;
    y = y / b;
    int c = (fac[x][2] <= 1000) ? g[fac[x][2]][y % fac[x][2]] : (y % fac[x][2] == 0) ? fac[x][2] : 1;
    return a * b * c;
}


void solve() {
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 1;i <= n;i++)cin >> b[i];
    for (int i = 1;i <= n;i++) {
        ll temp = 1;
        ll sum = 0;
        for (int j = 1;j <= n;j++) {
            temp = temp * i % MOD;
            sum = (sum + (ll)temp * getgcd(a[i], b[j]) % MOD) % MOD;
        }
        cout << sum << endl;
    }
}