#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace IO{
	template<typename T> inline void read(T &x){
		bool f=1;x=0;char ch=getchar();
		while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=getchar();}
		while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch&15),ch=getchar();
		x=f?x:-x;
	}
	template<typename T> inline void write(T x){
		if(x<0) putchar('-'),x=-x;
	   	if(x>9) write(x/10);
	   	putchar(('0'+x%10));
	}
	template <typename T,typename ...Args> inline void read(T &x,Args &...args){read(x);read(args...);}
	template<typename T> inline void write(T x,char c){write(x),putchar(c);}
}
using namespace IO;
const int mod=998244353;
struct query{
	int l,r,ans;
	query(){l=r=ans=0;}
}Q[200005];
int n,m,qwq,a[200005],f[200005][21];
void calc(int l,int r,vector<int> &q){
	if(l==r){
		int cnt=1;
		if(!(a[l]%m))cnt++;
		for(unsigned i=0;i<q.size();++i)Q[q[i]].ans=cnt;
		return;
	}
	int mid=(l+r)>>1;
	vector<int> qn[2];
	memset(f[mid],0,sizeof f[mid]);
	memset(f[mid+1],0,sizeof f[mid+1]);
	f[mid][0]++;f[mid][a[mid]%m]++;
	f[mid+1][0]++;f[mid+1][a[mid+1]%m]++;
	int tem[20];
	for(int i=mid-1;l<=i;--i){
		memset(tem,0,sizeof tem);
		for(int j=0;j<m;j++){
			tem[j]=(tem[j]+f[i+1][j])%mod;
			tem[(j+a[i])%m]=(tem[(j+a[i])%m]+f[i+1][j])%mod;
		}
		memcpy(f[i],tem,sizeof tem);
	}
	for(int i=mid+2;i<=r;++i){
		memset(tem,0,sizeof tem);
		for(int j=0;j<m;j++){
			tem[j]=(tem[j]+f[i-1][j])%mod;
			tem[(j+a[i])%m]=(tem[(j+a[i])%m]+f[i-1][j])%mod;
		}
		memcpy(f[i],tem,sizeof tem);
	}
	for(unsigned i=0;i<q.size();++i){
		if(Q[q[i]].r<=mid)qn[0].push_back(q[i]);
		if(mid<Q[q[i]].l) qn[1].push_back(q[i]);
		if(Q[q[i]].l<=mid&&mid<Q[q[i]].r)
			for(int j=0;j<m;++j)Q[q[i]].ans=(Q[q[i]].ans+f[Q[q[i]].l][j]*f[Q[q[i]].r][(m-j)%m])%mod;
	}
	if(qn[0].size())calc(l,mid,qn[0]);
	if(qn[1].size())calc(mid+1,r,qn[1]);
	return;
}
signed main(){
	read(n,m);
	for(int i=1;i<=n;++i)read(a[i]);
	read(qwq);
	vector<int> v;
	for(int i=1;i<=qwq;++i){
		read(Q[i].l,Q[i].r);
		v.push_back(i);
	}
	calc(1,n,v);
	for(int i=1;i<=qwq;++i)write(Q[i].ans,'\n');
	return 0;
}