//呃呃呃，为什么打不开codeforces别人的代码啊www，最后找了半天终于找到了题解 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+5,maxm=25,mod=998244353;

struct NODE{ int x,y,id; };
vector<NODE>q;
int m,a[maxn],ans[maxn];
ll f[maxn][maxm],f2[maxn][maxm];
void Solve(int l,int r,vector<NODE>q){
	if(l>r) return;
	if(l==r){
		for(int i=0;i<q.size();i++){
			if(!a[l]) ans[q[i].id]=2;
			else ans[q[i].id]=1;
		}
		return;
	}
	int mid=(l+r)>>1;
	for(int i=l;i<=r;i++)
		for(int j=0;j<m;j++)
			f[i][j]=f2[i][j]=0;
	f[mid+1][0]=1;
	for(int i=mid;i>=l;i--)//从 mid 往左DP
		for(int j=0;j<m;j++)
			f[i][j]=(f[i+1][j]+f[i+1][(j-a[i]+m)%m])%mod;
	f2[mid][0]=1;
	for(int i=mid+1;i<=r;i++)//从 mid+1 往右DP
		for(int j=0;j<m;j++)
			f2[i][j]=(f2[i-1][j]+f2[i-1][(j-a[i]+m)%m])%mod;
	vector<NODE>ql,qr;
	for(int i=0;i<q.size();i++){
		if(q[i].x<=mid&&q[i].y>mid){//处理这一层跨过 mid 的询问
			for(int j=0;j<m;j++)
				(ans[q[i].id]+=f[q[i].x][j]*f2[q[i].y][(m-j)%m]%mod)%=mod;
		}
		else if(q[i].y<=mid) ql.push_back(q[i]);
		else qr.push_back(q[i]);
	}
	Solve(l,mid,ql);
	Solve(mid+1,r,qr);
}

int main(){
	cin.tie(0) ; ios::sync_with_stdio(0);
	int n; cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]%=m;
	}
	int qt; cin>>qt;
	for(int i=1,x,y;i<=qt;i++){
		cin>>x>>y;
		q.push_back({x,y,i});
	}
	Solve(1,n,q);
	for(int i=1;i<=qt;i++)
		cout<<ans[i]<<"\n";
	return 0;
}

//https://blog.csdn.net/weixin_75161465/article/details/142733157