#include <bits/stdc++.h>
using namespace std;
#define int long long

int solveTestCase() {
    int n;
    cin >> n;

    string s = "989";
    if (n <= 3)
        return cout << s.substr(0, n) << "\n", 0;

    cout << s;
    for (int i = 3; i < n; i++)
        cout << (i - 3) % 10;
    cout << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    cin >> t;
    while (t--)
        solveTestCase();

}

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 3e5;
int a[N], n;

int isValley(int i) {
    return (i > 0 && i < n - 1 && a[i] < a[i - 1] && a[i] < a[i + 1]);
}

int isHill(int i) {
    return (i > 0 && i < n - 1 && a[i] > a[i - 1] && a[i] > a[i + 1]);
}

int solveTestCase() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];

    int is[n] = {};
    int s = 0;
    for (int i = 1; i < n - 1; i++) {
        if (isHill(i) || isValley(i))
            is[i] = 1, s++;
    }

    int ans = s;
    for (int i = 1; i < n - 1; i++) {
        int temp = a[i];
        a[i] = a[i - 1];
        ans = min(ans, s - is[i - 1] - is[i] - is[i + 1] + isHill(i - 1) + isValley(i - 1) + isHill(i) + isValley(i) + isHill(i + 1) + isValley(i + 1));
        a[i] = a[i + 1];
        ans = min(ans, s - is[i - 1] - is[i] - is[i + 1] + isHill(i - 1) + isValley(i - 1) + isHill(i) + isValley(i) + isHill(i + 1) + isValley(i + 1));
        a[i] = temp;
    }

    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    cin >> t;
    while (t--)
        solveTestCase();
}

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 3e5;
vector<vector<int>> a(3, vector<int>());
vector<int> n(3, 0);

int calc() {
    int ans = 0, m1 = a[1][0], m2 = a[2][0], s1 = 0, s2 = 0;
    for (int i : a[0]) ans += i;
    for (int i = 1; i < n[1]; i++) s1 += a[1][i];
    for (int i = 1; i < n[2]; i++) s2 += a[2][i];

    ans += max({s2 - m1 + s1 - m2, m2 + s2 - m1 - s1, m1 + s1 - m2 - s2});
    return ans;
}

int solveTestCase() {
    cin >> n[0] >> n[1] >> n[2];
    a[0].resize(n[0]);
    a[1].resize(n[1]);
    a[2].resize(n[2]);

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < n[i]; j++)
            cin >> a[i][j];
        sort(a[i].begin(), a[i].end());
    }

    int ans = -1e18;
    ans = max(ans, calc());

    swap(a[0], a[1]), swap(n[0], n[1]);
    ans = max(ans, calc());

    swap(a[0], a[2]), swap(n[0], n[2]);
    ans = max(ans, calc());

    cout << ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    //cin >> t;
    while (t--)
        solveTestCase();
}

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 5005, mod = 1e9 + 7;
int dp[N][N], cnt[N], a[N], q, n, k;

void pre() {
    for (int i = 0; i < n; i++)
        dp[i][0] = 1;
        
    for (int j = 1; j < N; j++) {
        dp[0][j] = dp[1][j - 1];
        for (int i = 1; i < n - 1; i++)
            dp[i][j] = (dp[i - 1][j - 1] + dp[i + 1][j - 1]) % mod;
        dp[n - 1][j] = dp[n - 2][j - 1];
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= k; j++)
            cnt[i] += dp[i][j] * dp[i][k - j], cnt[i] %= mod;
    }
}

void solveTestCase() {
    int ans = 0;
    for (int i = 0; i < n; i++)
        cin >> a[i], ans += a[i] * cnt[i], ans %= mod;
    
    while (q--) {
        int i, x;
        cin >> i >> x;
        i--;
        
        ans -= (a[i] * cnt[i]) % mod, ans += mod, ans %= mod;
        
        a[i] = x;
        ans += (a[i] * cnt[i]), ans %= mod;
        cout << ans << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> n >> k >> q;
    pre();
    
    int t = 1;
    //cin >> t;
    while (t--)
        solveTestCase();
}

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 5e5;
vector<int> adj[N];
int a[N], par[N], n;

map<int, vector<int>> v, times;
int euler[N * 2 - 1], tin[N], tout[N], c = 0;

set<pair<int, int>> g;
int dp[N], ans;

void dfs(int v, int p = -1) {
    par[v] = p;
    tin[v] = c;
    euler[c++] = v;

    for (int i : adj[v]) {
        if (i == p)
            continue;
        dfs(i, v);
        euler[c++] = v;
    }

    tout[v] = c - 1;
}

void examine(int v) {
    int sum = 0;

    for (int i : adj[v]) {
        if (i == par[v])
            continue;

        int count = upper_bound(times[a[v]].begin(), times[a[v]].end(), tout[i]) - lower_bound(times[a[v]].begin(), times[a[v]].end(), tin[i]);
        if (count > 0)
            g.insert({v, i});
        sum += count;
    }

    sum = times[a[v]].size() - sum - 1;
    if (sum)
        g.insert({v, par[v]});
}

int setup(int v) {
    for (int i : adj[v]) {
        if (i != par[v])
            dp[v] += setup(i);
    }
    return dp[v] + g.count({v, par[v]});
}

void reroot(int v) {
    if (dp[v] == g.size())
        ans++;

    for (int i : adj[v]) {
        if (i == par[v])
            continue;

        dp[v] -= dp[i];
        dp[v] -= g.count({i, v});
        dp[i] += dp[v];
        dp[i] += g.count({v, i});

        reroot(i);

        dp[i] -= g.count({v, i});
        dp[i] -= dp[v];
        dp[v] += g.count({i, v});
        dp[v] += dp[i];
    }
}

int solveTestCase() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(0);
    for (int i = 0; i < n; i++)
        v[a[i]].push_back(i);

    for (auto i : v) {
        if (i.second.size() == 1)
            continue;

        for (int j : i.second)
            times[i.first].push_back(tin[j]);
        sort(times[i.first].begin(), times[i.first].end());
        for (int j : i.second)
            examine(j);
    }

    setup(0);
    reroot(0);

    cout << ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    //cin >> t;
    while (t--)
        solveTestCase();
}