Untitled

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct Trie {
    static const int B = 31; // The number of bits we are considering, adjust based on your data type.

    struct node {
        node* nxt[2]; // Pointers to child nodes
        int sz; // The size/count of elements in the subtrie rooted at this node

        node() {
            nxt[0] = nxt[1] = nullptr;
            sz = 0;
        }
    }*root;

    Trie() {
        root = new node();
    }

    void insert(int val) {
        node* cur = root;
        cur->sz++;
        for (int i = B - 1; i >= 0; i--) {
            int b = (val >> i) & 1;
            if (cur->nxt[b] == nullptr) cur->nxt[b] = new node();
            cur = cur->nxt[b];
            cur->sz++;
        }
    }

    void erase(int val) {
        node* cur = root;
        cur->sz--;
        for (int i = B - 1; i >= 0; i--) {
            int b = (val >> i) & 1;
            cur = cur->nxt[b];
            cur->sz--;
        }
    }

    int query(int x, int k) { // Number of values such that val ^ x < k
        node* cur = root;
        int ans = 0;
        for (int i = B - 1; i >= 0; i--) {
            if (cur == nullptr) break;
            int b1 = (x >> i) & 1;
            int b2 = (k >> i) & 1;
            if (b2 == 1) {
                if (cur->nxt[b1]) ans += cur->nxt[b1]->sz;
                cur = cur->nxt[!b1];
            } else cur = cur->nxt[b1];
        }
        return ans;
    }

    int get_max(int x) { // Returns maximum of val ^ x
        node* cur = root;
        int ans = 0;
        for (int i = B - 1; i >= 0; i--) {
            int k = (x >> i) & 1;
            if (cur->nxt[!k]) {
                cur = cur->nxt[!k];
                ans = (ans << 1) | 1;
            } else {
                cur = cur->nxt[k];
                ans <<= 1;
            }
        }
        return ans;
    }

    int get_min(int x) { // Returns minimum of val ^ x
        node* cur = root;
        int ans = 0;
        for (int i = B - 1; i >= 0; i--) {
            int k = (x >> i) & 1;
            if (cur->nxt[k] && cur->nxt[k]->sz) {
                cur = cur->nxt[k];
                ans <<= 1;
            } else {
                cur = cur->nxt[!k];
                ans = (ans << 1) | 1;
            }
        }
        return ans;
    }

    void del(node* cur) {
        for (int i = 0; i < 2; i++)
            if (cur->nxt[i]) del(cur->nxt[i]);
        delete(cur);
    }
};

int cntSmaller(Trie::node* root, int N, int K) {
    int cntPairs = 0;

    for (int i = 30; i >= 0 && root; i--) {
        bool x = N & (1 << i);
        bool y = K & (1 << i);

        if (y) {
            if (root->nxt[x]) {
                cntPairs += root->nxt[x]->sz;
            }
            root = root->nxt[1 - x];
        } else {
            root = root->nxt[x];
        }
    }
    return cntPairs;
}
typedef long long ll;
const int N=1e4+5;
const int Qu=2e5+5;
const int SQ=100;
struct Query{
    int l,r,q_idx,blk_idx;
    Query(){}
    Query(int _l,int _r,int _q_idx)
    {
        l=_l,r=_r,q_idx=_q_idx,blk_idx=_l/SQ;
    }
    bool operator<(const Query&Q)const{
        if(blk_idx!=Q.blk_idx)
        {
            return blk_idx<Q.blk_idx;
        }
        return r<Q.r;
    }
};
ll n,q,k,arr[N],res=0,ans[Qu];Query qu[Qu];
Trie t;
map<int,int>frq;
ll calc(int idx)
{
    return arr[idx]*frq[arr[idx]]*frq[arr[idx]];
}
long long output=0;
void add(int idx)
{
    frq[arr[idx]]++;
    output+= cntSmaller(t.root,arr[idx],k);
    t.insert(arr[idx]);
}
void remove(int idx)
{
    frq[arr[idx]]--;
    t.erase(arr[idx]);
    output-= cntSmaller(t.root,arr[idx],k);
}
void MO_process()
{
    sort(qu,qu+q);
    int l=1,r=0;
    for(int i=0;i<q;i++)
    {
        while(l>qu[i].l) add(--l);
        while(r<qu[i].r) add(++r);
        while(l<qu[i].l) remove(l++);
        while(r>qu[i].r) remove(r--);
        ans[qu[i].q_idx]=output;
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--) {
        cin >> n >> k >> q;
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        for (int i = 0; i < q; i++) {
            int l, r;
            cin >> l >> r;
            qu[i] = Query(--l, --r, i);
        }
        MO_process();
        for (int i = 0; i < q; i++) {
            cout << ans[i] << ' ';
        }
        cout << '\n';
    }
    return 0;
}