import sys
input = sys.stdin.readline

P = 998244353

di = [[1, 1, 1, 0, 1, 1, 1],
     [0, 0, 1, 0, 0, 1, 0],
     [1, 0, 1, 1, 1, 0, 1],
     [1, 0, 1, 1, 0, 1, 1],
     [0, 1, 1, 1, 0, 1, 0],
     [1, 1, 0, 1, 0, 1, 1],
     [1, 1, 0, 1, 1, 1, 1],
     [1, 0, 1, 0, 0, 1, 0],
     [1, 1, 1, 1, 1, 1, 1],
     [1, 1, 1, 1, 0, 1, 1]]

inv100 = pow(100, P - 2, P)

t = int(input())
for _ in range(t):
    C = int(input())
    ps = list(map(int, input().split()))
    res = [0 for i in range(10)]

    for d in range(10):
        p1 = 1
        for i in range(7):
            if di[d][i]:
                p1 = p1 * ps[i] % P * inv100 % P
            else:
                p1 = p1 * (1 + P - ps[i] * inv100 % P) % P
        res[d] = p1

    f = [1 for i in range(C + 1)]
    for v in range(C + 1):
        x = v
        p = 1000
        for i in range(4):
            f[v] = f[v] * res[x // p] % P
            x %= p
            p //= 10

    ans = 0
    for v in range(C + 1):
        ans = (ans + f[v] * f[C - v] % P) % P
    print(ans)

#include "bits/stdc++.h"

using namespace std;
using i64 = int64_t;

constexpr int P = 998244353;

i64 power(i64 a, int b, int p = P) {
    i64 r = 1;
    for (; b > 0; b >>= 1, a = a * a % p) {
        if (b & 1) {
            r = r * a % p;
        }
    }
    return r;
}
const i64 inv100 = power(100, P - 2);

short di[10][7] = {
    {1, 1, 1, 0, 1, 1, 1},
    {0, 0, 1, 0, 0, 1, 0},
    {1, 0, 1, 1, 1, 0, 1},
    {1, 0, 1, 1, 0, 1, 1},
    {0, 1, 1, 1, 0, 1, 0},
    {1, 1, 0, 1, 0, 1, 1},
    {1, 1, 0, 1, 1, 1, 1},
    {1, 0, 1, 0, 0, 1, 0},
    {1, 1, 1, 1, 1, 1, 1},
    {1, 1, 1, 1, 0, 1, 1}
};

void solve() {
    int c;
    cin >> c;
    vector<int> ps(7);
    for (int &pi : ps) {
        cin >> pi;
    }

    vector<i64> g(10);
    for (int d = 0; d < 10; d++) {
        i64 p1 = 1;
        for (int i = 0; i < 7; i++) {
            if (di[d][i]) {
                p1 = p1 * ps[i] % P * inv100 % P;
            } else {
                p1 = p1 * (1 + P - ps[i] * inv100 % P) % P;
            }
        }
        g[d] = p1;
    }

    vector<i64> f(c + 1, 1);
    for (int v = 0; v <= c; v++) {
        int x = v;
        for (int i = 0, p = 1000; i < 4; i++, p /= 10) {
            f[v] = f[v] * g[x / p] % P;
            x %= p;
        }
    }

    i64 ans = 0;
    for (int v = 0; v <= c; v++) {
        ans = (ans + f[v] * f[c - v] % P) % P;
    }
    cout << ans << '\n';
}

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

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

import sys
input = sys.stdin.readline

P = 998244353
N = 200000

fac = [0] * (N + 1)
fac[0] = 1
for i in range(1, N + 1):
    fac[i] = fac[i - 1] * i % P

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    
    cnt = 0
    mn = min(b)
    for x in a:
        if x > mn:
            cnt += 1
    print(fac[cnt] * fac[n - cnt] % P)

#include "bits/stdc++.h"

using namespace std;
using i64 = int64_t;

constexpr int P = 998244353;
constexpr int N = 200000;

i64 fac[N + 1];

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }

    int cnt = 0;
    int mn = *min_element(b.begin(), b.end());
    for (int x : a) {
        if (x > mn) {
            cnt++;
        }
    }
    cout << fac[cnt] * fac[n - cnt] % P << '\n';
}

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

    fac[0] = 1;
    for (int i = 1; i <= N; i++) {
        fac[i] = fac[i - 1] * i % P;
    }

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    print((n - 2) * max(a) + a[0] + a[n - 1])

#include "bits/stdc++.h"

using namespace std;
using i64 = int64_t;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    cout << i64(n - 2) * *max_element(a.begin(), a.end()) + a[0] + a[n - 1] << '\n';
}

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

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    if sum(1 for x in a if x > 0) <= k:
        print(0)
    else:
        def check(t):
            time = [0 for i in range(n)]
            used = 0
            best = -1
            mx = -1
            for i in range(n):
                if a[i] == 0:
                    continue

                if mx < i:
                    used += 1
                    mx = max(best, i + a[i])
                    for j in range(i + 1, min(n, mx + 1)):
                        time[j] = 1
                else:
                    if time[i] < t:
                        for j in range(mx + 1, min(n, i + a[i] + 1)):
                            time[j] = time[i] + 1
                        mx = max(mx, i + a[i])
                    else:
                        best = max(best, i + a[i])
            return used <= k
        
        lo, hi, ans = 1, n, -1
        while lo <= hi:
            mid = (lo + hi) // 2
            if check(mid):
                hi = mid - 1
                ans = mid
            else:
                lo = mid + 1

        print(ans)

#include "bits/stdc++.h"

using namespace std;

void solve() {
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		cnt += a[i] > 0;
	}
	
	if (cnt <= k) {
		cout << "0\n";
		return;
	}

	auto check = [&](int t) {
		vector<int> time(n);
		int used = 0, mx = -1, best = -1;
		for (int i = 0; i < n; ++i) {
			if (!a[i]) {
				continue;
			}
			if (mx < i) {
				used++;
                mx = max(best, i + a[i]);
				for (int j = i + 1; j < min(n, mx + 1); j++) {
                    time[j] = 1;
                }
			} else {
				if (time[i] < t) {
					for (int j = mx + 1; j < min(n, i + a[i] + 1); j++) {
						time[j] = time[i] + 1;
					}
					mx = max(mx, i + a[i]);
				} else {
                    best = max(best, i + a[i]);
				}
			}
		}
		return used <= k;
	};

	int lo = 1, hi = n, ans = -1;
	while (lo <= hi) {
		int mid = (lo + hi) / 2;
		if (check(mid)) {
			hi = mid - 1;
			ans = mid;
		} else {
			lo = mid + 1;
		}
	}
	cout << ans << '\n';
}

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

	int t;
	cin >> t;
	while (t--) {
		solve();
	}

	return 0;
}

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    ans = max(k + a[n - 1], k + a[0])
    for i in range(n - 1):
        ans = max(ans, a[i] + a[i + 1])
    print(ans)

#include "bits/stdc++.h"

using namespace std;
using i64 = int64_t;

void solve() {
    int n, k;
    cin >> n >> k;

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

    int ans = max(k + a[n - 1], k + a[0]);
    for (int i = 0; i + 1 < n; i++) {
        ans = max(ans, a[i] + a[i + 1]);
    }
    cout << ans << '\n';
}

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

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

import sys
input = sys.stdin.readline

def rev(x):
    return int(str(x)[::-1])

t = int(input())
for _ in range(t):
    l, r = map(int, input().split())
    ans = rev(r)
    if r > l:
        ans = max(ans, rev(r - 1))
    p = 10
    while p <= r:
        x = r // p * p - 1
        if l <= x <= r:
            ans = max(ans, rev(x))
        p *= 10
    print(ans)

#include "bits/stdc++.h"

using namespace std;
using i64 = int64_t;

i64 rev(i64 x) {
    string s = to_string(x);
    reverse(s.begin(), s.end());
    return stoll(s);
}

void solve() {
	i64 l, r;
	cin >> l >> r;

	i64 ans = rev(r);
	if (r > l) {
		ans = max(ans, rev(r - 1));
	}
 	for (i64 p = 10; p <= r; p *= 10) {
		i64 x = r / p * p - 1;
		if (x >= l && x <= r) {
			ans = max(ans, rev(x));
		}
	}
	cout << ans << '\n';
}

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

	int t;
	cin >> t;
	while (t--) {
		solve();
	}

	return 0;
}

import sys
input = sys.stdin.readline

P = 998244353

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))

    dp = [0 for i in range(n + 1)]
    pre = [0 for i in range(n + 1)]

    dp[0] = 1
    pre[0] = 1

    last = [0 for i in range(32)]

    l = 1
    for i in range(n):
        for b in range(32):
            if a[i] >> b & 1:
                if last[b] + 1 > l:
                    l = last[b] + 1

        left = 0
        j = l - 2
        if j >= 0:
            left = pre[j]
        dp[i + 1] = ((pre[i] - left) % P + P) % P
        pre[i + 1] = (pre[i] + dp[i + 1]) % P
        for b in range(32):
            if a[i] >> b & 1:
                last[b] = i + 1
    print(dp[n])

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    if n == 1:
        print("YES\n1")
    elif n == 3:
        print("YES\n1 2 3")
    else:
        print("NO")

#include "bits/stdc++.h"

using namespace std;
using i64 = int64_t;

void solve() {
    int n;
    cin >> n;

    if (n == 1) {
        cout << "YES\n1\n";
    } else if (n == 3) {
        cout << "YES\n1 2 3\n";
    } else {
        cout << "NO\n";
    }
}

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

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

import sys
input = sys.stdin.readline

n = int(input())

if n % 10 == 0:
    print(1)
elif n % 10 == 5:
    print(2)
elif n % 10 % 2 == 0:
    print(5)
else:
    print(10)

#include "bits/stdc++.h"

using namespace std;
using i64 = int64_t;

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

    int n;
    cin >> n;
    if (n % 10 == 0) {
        cout << "1\n";
    } else if (n % 10 == 5) {
        cout << "2\n";
    } else if (n % 10 % 2 == 0) {
        cout << "5\n";
    } else {
        cout << "10\n";
    }
    
    return 0;
}