// Problem: D. 子序列
// Contest: undefined - NOIP2024训练赛 03
// URL: http://noi.ac/contest/1155/problem/2770
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Challenger: Erica N
// ----
// 
#include<bits/stdc++.h>

using namespace std;
#define rd read()
#define ull unsigned long long
#define int long long 
#define pb push_back
#define itn int
#define ps second 
#define pf first


#define rd read()
int read(){
  int xx = 0, ff = 1;char ch = getchar();
  while (ch < '0' || ch > '9'){
    if (ch == '-')ff = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')xx = xx * 10 + (ch - '0'), ch = getchar();
  return xx * ff;
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() {cerr << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
	for (auto v: a) cerr << v << ' ';err(x...);
}
template<typename T, typename... A>
void err(T a, A... x) {
	cerr << a << ' ';err(x...);
}
#else
#define dbg(...)
#endif
const int N=2e5+5;
const ull P=137;
const int INF=1e18+7;
/*

策略


*/	


int n,m;
int a[N];

namespace SGT{
	
	struct Node{
		int a[22];
		
		void init(){
			memset(a,0,sizeof a);
		}
	}t[N<<2];//区间内和%m=j的序列个数
	
	Node merge(Node a,Node b){
		Node c;
		c.init();
		for(int i=0;i<m;i++){
			for(int j=0;j<m;j++){
				c.a[(i+j)%m]+=a.a[j]*b.a[i];
				
			}
			c.a[i]+=a.a[i]+b.a[i];
		}
		return c;
	}
	
	void build(int x,int l,int r){
		if(l==r){
			t[x].a[a[l]%m]++;
			return ;
		}
		
		int mid=l+r>>1;
		build(x<<1,l,mid);
		build(x<<1|1,mid+1,r);
		
		t[x]=merge(t[x<<1],t[x<<1|1]);
		
	}
	
	Node query(int x,int l,int r,int pl,int pr){
		if(pl<=l&&pr>=r)return t[x];
		int mid=l+r>>1;
		int fl=0,fr=0;
		Node nl,nr;
		if(pl<=mid)fl=1,nl=query(x<<1,l,mid,pl,pr);
		if(pr>mid)fr=1,nr=query(x<<1|1,mid+1,r,pl,pr);
		if(fl+fr==1){
			if(fl)return nl;
			return nr;
		}
		return merge(nl,nr);
	}
}using namespace SGT;

signed main(){
	 n=rd,m=rd;
	for(int i=1;i<=n;i++){
		a[i]=rd;
	}
	
	
	build(1,1,n);
	
	// cdbg("OK");
	int q=rd;
	while(q--){
		int a=rd,b=rd;
		cout<<query(1,1,n,a,b).a[0]+1<<'\n';
	}
	
	
}