Untitled

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
// ------------------------MeMe-----------------------//

template<class T> struct SegTree {
    T GAR = 0;
    int sz;
    vector<T> t , lz;
    SegTree() {}
    SegTree(int n) {
        sz = 1; while (sz < n) sz *= 2;
        t.resize(2 * sz, GAR);
        lz.resize(2 * sz, GAR);
    }
 
    T merge(T a, T b) { return a + b; }
 
    void lol(int k, int s, int e) {
        if (lz[k] == GAR) return;
        t[k] = merge(t[k], lz[k] * (e - s + 1));
        if(s != e) {
            lz[2*k] = merge(lz[2*k], lz[k]);
            lz[2*k+1] = merge(lz[2*k+1], lz[k]);
        }
        lz[k] = GAR;
    }
 
    T update(int l, int r, T v, int k = 1 , int s = 0, int e = -1) {
        if (e == -1) e = sz - 1;
        lol(k, s, e);
        if(s > r || e < l) return t[k];
        if(l <= s && e <= r) {
            lz[k] = v;
            return merge(t[k] , lz[k] * (e - s + 1));
        }
        int mid = (s+e)>>1;
        T ch1 = update(l, r, v, k*2, s, mid);
        T ch2 = update(l, r, v, k*2+1, mid+1, e);
        return t[k] = merge(ch1 , ch2);
    }
    T get(int l , int r, int k = 1, int s = 0 , int e = -1) {
        if (e == -1) e = sz - 1;
        lol(k, s, e);
        if(s > r || e < l) return GAR;
        if(l <= s && e <= r) return t[k];
        int mid = (s+e)>>1;
        T ch1 = get(l, r, k*2, s, mid);
        T ch2 = get(l, r, k*2+1, mid+1, e);
        return merge(ch1 , ch2);
    }
};
 
void code() {
    int n, k; cin >> n >> k;
    int a[n + 1]; a[0] = 0;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    vector<vector<pair<int, int>>>v(n + 1);
    SegTree<int> seg(n + 1);
    int q ; cin >> q;
    for (int i = 0; i < q; ++i){
        int l, r; cin >> l >> r;
        v[r].emplace_back(make_pair(l, i));
    }
    int ans[q] = {};
    map<int ,int> pos,pos_end;
    pos[0] = 1;
    pos_end[0] = 1;
    for (int i = 1; i <= n; ++i){
        a[i] += a[i - 1];
        int cur_val = a[i] - k;
        if (pos[cur_val] != 0){
            seg.update(pos[cur_val] ,pos_end[cur_val], 1);
        }
        
        for (auto &[l, index] : v[i]){
            ans[index] = seg.get(l, i);
        }
        if (pos[a[i]] == 0)
            pos[a[i]] = i + 1;
        pos_end[a[i]] = i + 1;
    }
    for (int i = 0 ; i < q; ++i) cout << ans[i] << '\n';
}

int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("err.txt", "w", stderr);
    #endif

    int tt = 1;
    cin >> tt;
    for (int tn = 1 ; tn <= tt ; tn++) {
        #ifndef ONLINE_JUDGE
        cout << "_________Test_" << tn << "_________" << endl;
        cerr << "_________Test_" << tn << "_________" << endl;
        #endif
        code();
    }

    #ifndef ONLINE_JUDGE
    cout << "________________________" ;
    cerr << "________________________" ;
    #endif
    return 0;
}