Untitled

#include <iostream>

using namespace std;

int sum(int n){
    int res = 0;
    while(n){
        res += n%10;
        n/=10;
    }
    return res;
}

int main(){
    freopen("BAI2.INP","r",stdin);
    freopen("BAI2.OUT","w",stdout);

    int n, q, l, r;
    cin >> n >> q;
    int a[n];
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++){
        if(a[i] % sum(a[i]) == 0)
            a[i] = 1;
        else a[i] = 0;
    }
    int pfs[n+1] = {0};
    for(int i = 1; i <= n; i++){
        pfs[i] += pfs[i-1] + a[i-1];
    }
    
    while(q--){
        cin >> l >> r;
        cout << pfs[r] - pfs[l-1] << endl;
    }
    return 0;
}