#include <bits/stdc++.h>
#define int long long
#define MOD 998244353
using namespace std;
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
int n, m, qq, a[200001], l[200001], r[200001], ans[200001];
struct node
{
    int x[20];
    node() { memset(x, 0, sizeof(x)); }
};
vector<int> q;
void solve(int L, int R, vector<int> v)
{
    if (L > R)
        return;
    if (L == R)
    {
        for (auto x : v)
        {
            if (a[L] % m)
                ans[x] = 1;
            else
                ans[x] = 2;
        }
        return;
    }
    vector<int> nowl, nowr;
    vector<node> prel, prer;
    node ll, rr;
    int mid = (L + R) >> 1;
    ll.x[0] = 1;
    ll.x[a[mid] % m]++;
    rr.x[0] = 1;
    rr.x[a[mid + 1] % m]++;
    prel.push_back(ll);
    prer.push_back(rr);
    for (int i = 1; mid - i >= L; i++)
    {
        node last = prel[i - 1];
        for (int j = 0; j < m; j++)
        {
            last.x[(j + a[mid - i]) % m] = (last.x[(j + a[mid - i]) % m] + prel[i - 1].x[j]) % MOD;
        }
        prel.push_back(last);
    }
    for (int i = 1; mid + 1 + i <= R; i++)
    {
        node last = prer[i - 1];
        for (int j = 0; j < m; j++)
        {
            last.x[(j + a[mid + 1 + i]) % m] = (last.x[(j + a[mid + 1 + i]) % m] + prer[i - 1].x[j]) % MOD;
        }
        prer.push_back(last);
    }
    for (auto x : v)
    {
        if (r[x] <= mid)
        {
            nowl.push_back(x);
        }
        else if (l[x] >= mid + 1)
        {
            nowr.push_back(x);
        }
        else
        {
            for (int i = 0; i < m; i++)
            {
                ans[x] = (ans[x] + (prel[mid - l[x] + 1 - 1].x[i] * prer[r[x] - mid - 1].x[(m - i) % m] % MOD)) % MOD;
            }
        }
    }
    solve(L, mid, nowl);
    solve(mid + 1, R, nowr);
}
signed main()
{
    n = read();
    m = read();
    for (int i = 1; i <= n; i++)
    {
        a[i] = read();
    }
    scanf("%lld", &qq);
    for (int i = 1; i <= qq; i++)
    {
        l[i] = read();
        r[i] = read();
        q.push_back(i);
    }
    solve(1, n, q);
    for (int i = 1; i <= qq; i++)
    {
        printf("%lld\n", ans[i]);
    }
    return 0;
}