#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 2e5 + 5;
int a[MAXN];
int A0[MAXN];
int A1[MAXN];
int AD_[MAXN];
 
void solve() {
    int n, q;
    if (!(cin >> n >> q)) return;
 
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
 
    A0[0] = 0;
    A1[0] = 0;
    AD_[0] = 0;
 
    for (int i = 0; i < n; ++i) {
        A0[i + 1] = A0[i] + (a[i] == 0);
        A1[i + 1] = A1[i] + (a[i] == 1);
    }
 
    for (int i = 0; i < n - 1; ++i) {
        AD_[i + 1] = AD_[i] + (a[i] == a[i + 1]);
    }
 
    for (int k = 0; k < q; ++k) {
        int l, r;
        if (!(cin >> l >> r)) return;
 
        int count0 = A0[r] - A0[l - 1];
        int count1 = A1[r] - A1[l - 1];
 
        int total_cost = -1;
 
        if (count0 % 3 == 0 && count1 % 3 == 0) {
            int total_ops = (int)(count0 / 3) + (int)(count1 / 3);
 
            total_cost = total_ops;
 
            if (count0 == count1) {
 
                int adjacent_equal_count = AD_[r - 1] - AD_[l - 1];
 
                if (adjacent_equal_count == 0) {
                    total_cost += 1;
                }
            }
        }
 
        cout << total_cost << "\n";
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
 
    return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpjb25zdCBpbnQgTUFYTiA9IDJlNSArIDU7CmludCBhW01BWE5dOwppbnQgQTBbTUFYTl07CmludCBBMVtNQVhOXTsKaW50IEFEX1tNQVhOXTsKCnZvaWQgc29sdmUoKSB7CiAgICBpbnQgbiwgcTsKICAgIGlmICghKGNpbiA+PiBuID4+IHEpKSByZXR1cm47CgogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyArK2kpIHsKICAgICAgICBjaW4gPj4gYVtpXTsKICAgIH0KCiAgICBBMFswXSA9IDA7CiAgICBBMVswXSA9IDA7CiAgICBBRF9bMF0gPSAwOwoKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgKytpKSB7CiAgICAgICAgQTBbaSArIDFdID0gQTBbaV0gKyAoYVtpXSA9PSAwKTsKICAgICAgICBBMVtpICsgMV0gPSBBMVtpXSArIChhW2ldID09IDEpOwogICAgfQoKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbiAtIDE7ICsraSkgewogICAgICAgIEFEX1tpICsgMV0gPSBBRF9baV0gKyAoYVtpXSA9PSBhW2kgKyAxXSk7CiAgICB9CgogICAgZm9yIChpbnQgayA9IDA7IGsgPCBxOyArK2spIHsKICAgICAgICBpbnQgbCwgcjsKICAgICAgICBpZiAoIShjaW4gPj4gbCA+PiByKSkgcmV0dXJuOwoKICAgICAgICBpbnQgY291bnQwID0gQTBbcl0gLSBBMFtsIC0gMV07CiAgICAgICAgaW50IGNvdW50MSA9IEExW3JdIC0gQTFbbCAtIDFdOwoKICAgICAgICBpbnQgdG90YWxfY29zdCA9IC0xOwoKICAgICAgICBpZiAoY291bnQwICUgMyA9PSAwICYmIGNvdW50MSAlIDMgPT0gMCkgewogICAgICAgICAgICBpbnQgdG90YWxfb3BzID0gKGludCkoY291bnQwIC8gMykgKyAoaW50KShjb3VudDEgLyAzKTsKCiAgICAgICAgICAgIHRvdGFsX2Nvc3QgPSB0b3RhbF9vcHM7CgogICAgICAgICAgICBpZiAoY291bnQwID09IGNvdW50MSkgewoKICAgICAgICAgICAgICAgIGludCBhZGphY2VudF9lcXVhbF9jb3VudCA9IEFEX1tyIC0gMV0gLSBBRF9bbCAtIDFdOwoKICAgICAgICAgICAgICAgIGlmIChhZGphY2VudF9lcXVhbF9jb3VudCA9PSAwKSB7CiAgICAgICAgICAgICAgICAgICAgdG90YWxfY29zdCArPSAxOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICBjb3V0IDw8IHRvdGFsX2Nvc3QgPDwgIlxuIjsKICAgIH0KfQoKaW50IG1haW4oKSB7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGNpbi50aWUoTlVMTCk7CgogICAgaW50IHQ7CiAgICBjaW4gPj4gdDsKICAgIHdoaWxlICh0LS0pIHsKICAgICAgICBzb2x2ZSgpOwogICAgfQoKICAgIHJldHVybiAwOwp9

MgoxMiA0CjAgMCAxIDEgMCAxIDAgMSAwIDEgMSAwCjEgMTIKMiA3CjUgMTAKNiAxMQo2IDMKMCAwIDAgMSAxIDEKMSAzCjQgNgoxIDYK

2
12 4
0 0 1 1 0 1 0 1 0 1 1 0
1 12
2 7
5 10
6 11
6 3
0 0 0 1 1 1
1 3
4 6
1 6