// 律己则安，越是执着，便是越苦;
// 安下心来，看该看的风景，做该做的事。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define pii pair<int, int>
#define int long long
#define pb push_back
#define se second
#define fi first
double pi = acos(-1);
const int N = 2e5 + 10, mod = 1e9+7, inf = 1e18 + 5;
void solve() {
    int n,q; cin >> n >> q;
    vector<int> a(n+1),pre(n+1),d(n+1); 
    // 等价于int a[n+1], int pre[n+1], int d[n+1];
    // pre：1的前缀和（用于判断1的个数是否为3的倍数）；
    // d：相邻元素不同的次数的前缀和
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        pre[i] = pre[i-1] + a[i]; // 计算1的前缀和，判断1的个数是否为3的倍数
    }
    for(int i = 1; i < n; i++){
        d[i] = d[i - 1] + (a[i] != a[i + 1]); // 统计相邻元素不同的次数，前缀和形式存储
    }
    d[n] = d[n - 1]; // 统一数组长度，方便后续查询
    while(q--){
        int l,r; cin >> l >> r; 
        int m = r - l + 1;
        // 可行性判断：长度是3的倍数 + 1的个数是3的倍数
        if(m % 3 != 0 || (pre[r] - pre[l-1]) % 3 != 0){
            cout << -1 << '\n';
            continue;
        }
        // 判断是否严格交替，进而计算最小代价
        cout << ((d[r-1] - d[l-1] == m - 1) ? (m/3 + 1) : (m/3)) << '\n';
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}