D 偶数

手算几下会发现：实际上不用处理整个串，只需要关注一半的串即可。并且串的构成遵循一定规律。

我们先用 KMP 算出一半的串（记为 ）的 border，记其长度为 。记 的长度为 。

如果这是个周期串就很好办，下面考虑非周期串的情况。

考虑把扩展到足够长的串切分成若干段，如下所示。

即：第 段完全由前 段复制而来。第 1 段为 ，第 2 段为 。

然后会发现第 段的长度为 ，其中 是斐波那契数列，。

由于 的斐波那契数不超过 100 个，因此可知这样的段数不会很多，故可以先预处理出每一段的前缀和，然后每次询问时暴力累加贡献，详细见代码。

#include <bits/stdc++.h>
#define MOD 998244353
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
typedef long long ll;
inline int lowbit(int x){
    return x & (-x);
}
inline int modadd(int x, int y){
    return (x + y >= MOD ? x + y - MOD: x + y);
}
int poww(int a, int b){
    int res = 1;
    while (b > 0){
        if (b & 1) res = 1ll * res * a % MOD;
        a = 1ll * a * a % MOD, b >>= 1;
    }
    return res;
}
inline int ten(ll x){
    return poww(10, x % (MOD - 1));
}
ll n;
int q, l, b;
char s[100005];
int nxt[100005];
int ans_basic[100005];
void init(){
    scanf("%s%lld%d", s, &n, &q);
    l = strlen(s);
    nxt[0] = -1;
    for (int i = 1, j = -1; i < l; ++i){
        while (j != -1 && s[j + 1] != s[i])
            j = nxt[j];
        if (s[j + 1] == s[i]) nxt[i] = ++j;
        else nxt[i] = -1;
    }
    l >>= 1;
    b = nxt[l - 1] + 1;
    ans_basic[0] = 0;
    REP(i, 1, l)
        ans_basic[i] = modadd(10ll * ans_basic[i - 1] % MOD, s[i - 1] - '0');
}
int query2(ll r){
    if (r == 0ll) return 0;
    ll cntt = r / (l - b), rem = r % (l - b);
    int qqq = ten(l - b);
    int res = 1ll * modadd(poww(qqq, cntt % (MOD - 1)), MOD - 1) * 
        poww(modadd(qqq, MOD - 1), MOD - 2) % MOD;
    res = 1ll * res * ans_basic[l - b] % MOD;
    res = 1ll * res * ten(rem) % MOD;
    res = modadd(res, ans_basic[rem]);
    return res;
}
void solve1(){
    // periodic
    // cout << l << " " << l - b << endl;
    while (q--){
        ll _a, _b;
        scanf("%lld%lld", &_a, &_b);
        int ans = query2(_b);
        --_a;
        int ans2 = 1ll * query2(_a) * ten(_b - _a) % MOD;
        ans = modadd(ans, MOD - ans2);
        printf("%d\n", ans);
    }
}

ll slen[205], sum[205];
int slen_sz;
int ans_slen[205];
int query(ll r){
    if (r <= l) return ans_basic[r];
    int pos = lower_bound(sum, sum + slen_sz + 1, r) - sum;
    if (sum[pos] == r) return ans_slen[pos];
    ll rem = r - sum[pos - 1];
    int res = modadd(query(rem), 1ll * ans_slen[pos - 1] * ten(rem) % MOD);
    return res;
}
void solve2(){
    // non-periodic
    // cout << l << " " << b << endl;
    slen_sz = 3;
    slen[0] = 0, slen[1] = l - b, slen[2] = b, slen[3] = l - b;
    sum[0] = 0, sum[1] = l - b, sum[2] = l, sum[3] = l + l - b;
    while (sum[slen_sz] < n){
        ll cur = slen[slen_sz - 1] + slen[slen_sz];
        slen[++slen_sz] = cur;
        sum[slen_sz] = sum[slen_sz - 1] + cur;
    }

    ans_slen[0] = 0;
    ans_slen[1] = ans_basic[l - b];
    ans_slen[2] = ans_basic[l];
    REP(i, 3, slen_sz)
        ans_slen[i] = modadd(ans_slen[i - 2], 
            1ll * ans_slen[i - 1] * ten(slen[i]) % MOD);

    while (q--){
        ll _a, _b;
        scanf("%lld%lld", &_a, &_b);
        int ans = query(_b);
        --_a;
        int ans2 = 1ll * query(_a) * ten(_b - _a) % MOD;
        ans = modadd(ans, MOD - ans2);
        printf("%d\n", ans);
    }
}
int main(){
    int T;
    scanf("%d", &T);
    while (T--){
        init();
        if (l % (l - b) == 0) solve1();
        else solve2();
    }
    return 0;
}