#include<bits/stdc++.h>
#include<bitset>
#define int long long
using namespace std;

const int N=4e5+5,INF=(1<<30);
int n,q;
string s;

struct nod{
    char front1,front2,last1,last2;
    int min110,min101,min001,min010;
    bool lazy;
    int l,r;
};

struct LTREE{
    nod tree[4*N+5];
    void init(){
        for(int i=0;i<=4*N;i++){
            tree[i].min001=tree[i].min010=INF;
            tree[i].min101=tree[i].min110=INF;
        }
    }
    void pushup(int l,int r,int pos){
        tree[pos].min001=min(tree[pos<<1].min001,tree[pos<<1|1].min001);
        tree[pos].min101=min(tree[pos<<1].min101,tree[pos<<1|1].min101);
        tree[pos].min110=min(tree[pos<<1].min110,tree[pos<<1|1].min110);
        tree[pos].min010=min(tree[pos<<1].min010,tree[pos<<1|1].min010);
        if(r-l+1==3){
            if(tree[pos<<1].r-tree[pos<<1].l+1==2){
                tree[pos].front1=tree[pos<<1].front1;
                tree[pos].front2=tree[pos<<1].front2;
                tree[pos].last1=tree[pos<<1|1].last1;
                tree[pos].last2=tree[pos<<1].front2;
            }else{
                tree[pos].front1=tree[pos<<1].front1;
                tree[pos].front2=tree[pos<<1|1].front1;
                tree[pos].last1=tree[pos<<1|1].last1;
                tree[pos].last2=tree[pos<<1|1].last2;
            }
            char a=tree[pos].front1,b=tree[pos].front2,c=tree[pos].last1;
            if(a=='1'&&b=='1'&&c=='0'){
                tree[pos].min110=min(tree[pos].min110,tree[pos<<1|1].r);
            }
            else if(a=='0'&&b=='1'&&c=='0'){
                tree[pos].min010=min(tree[pos].min010,tree[pos<<1|1].r);
            }
            else if(a=='0'&&b=='0'&&c=='1'){
                tree[pos].min001=min(tree[pos].min001,tree[pos<<1|1].r);
            }
            else if(a=='1'&&b=='0'&&c=='1'){
                tree[pos].min101=min(tree[pos].min101,tree[pos<<1|1].r);            
            }
            return;
        }
        if(r-l+1==2){
            tree[pos].front1=tree[pos<<1].front1;
            tree[pos].front2=tree[pos<<1|1].front1;
            tree[pos].last1=tree[pos<<1|1].last1;
            tree[pos].last2=tree[pos<<1].last1;
            return;
        }
        tree[pos].front2=tree[pos<<1].front2;
        tree[pos].last2=tree[pos<<1|1].last2;
        tree[pos].front1=tree[pos<<1].front1;
        tree[pos].last1=tree[pos<<1|1].last1;          
        char a=tree[pos<<1].last2,b=tree[pos<<1].last1;
        char c=tree[pos<<1|1].front1,d=tree[pos<<1|1].front2;
        if(a=='1'&&b=='1'&&c=='0'){
            tree[pos].min110=min(tree[pos].min110,tree[pos<<1|1].l);
        }
        else if(a=='0'&&b=='1'&&c=='0'){
            tree[pos].min010=min(tree[pos].min010,tree[pos<<1|1].l);
        }
        else if(a=='0'&&b=='0'&&c=='1'){
            tree[pos].min001=min(tree[pos].min001,tree[pos<<1|1].l);
        }
        else if(a=='1'&&b=='0'&&c=='1'){
            tree[pos].min101=min(tree[pos].min101,tree[pos<<1|1].l);            
        }

        if(b=='1'&&c=='1'&&d=='0'){
            tree[pos].min110=min(tree[pos].min110,tree[pos<<1|1].l+1);
        }
        else if(b=='0'&&c=='1'&&d=='0'){
            tree[pos].min010=min(tree[pos].min010,tree[pos<<1|1].l+1);
        }
        else if(b=='0'&&c=='0'&&d=='1'){
            tree[pos].min001=min(tree[pos].min001,tree[pos<<1|1].l+1);
        }
        else if(b=='1'&&c=='0'&&d=='1'){
            tree[pos].min101=min(tree[pos].min101,tree[pos<<1|1].l+1);
        }
    }
    void pushdown(int pos){
        if(!tree[pos].lazy)return;
        swap(tree[pos].min001,tree[pos].min110);
        swap(tree[pos].min010,tree[pos].min101);
        tree[pos].front1=(tree[pos].front1=='1'?'0':'1');
        tree[pos].front2=(tree[pos].front2=='1'?'0':'1');
        tree[pos].last1=(tree[pos].last1=='1'?'0':'1');
        tree[pos].last2=(tree[pos].last2=='1'?'0':'1');        
        tree[pos].lazy=0;
        tree[pos<<1].lazy^=1;
        tree[pos<<1|1].lazy^=1;
    }
    void build(int l=1,int r=n,int pos=1){
        tree[pos].l=l,tree[pos].r=r;
        if(l==r){
            tree[pos].front1=tree[pos].front2=s[l];
            tree[pos].last1=tree[pos].last2=s[r];
            return;
        }
        int mid=(l+r)>>1;
        build(l,mid,pos<<1);
        build(mid+1,r,pos<<1|1);
        pushup(l,r,pos);
    }
    void change(int x,int y,int l=1,int r=n,int pos=1){
        if(x<=l&&r<=y){
            swap(tree[pos].min001,tree[pos].min110);
            swap(tree[pos].min010,tree[pos].min101);
            tree[pos].front1=(tree[pos].front1=='1'?'0':'1');
            tree[pos].front2=(tree[pos].front2=='1'?'0':'1');
            tree[pos].last1=(tree[pos].last1=='1'?'0':'1');
            tree[pos].last2=(tree[pos].last2=='1'?'0':'1');
            tree[pos].lazy^=1;
            return;
        }
        pushdown(pos);
        int mid=(l+r)>>1;
        if(x<=mid)change(x,y,l,mid,pos<<1);
        if(y>mid)change(x,y,mid+1,r,pos<<1|1);
        pushup(l,r,pos);
    }
}tree;

void solve4(){
    cin>>n>>q>>s;
    s=" "+s;
    tree.init();
    tree.build();
    vector<int> vans;
    int ans_val;
    if (tree.tree[1].min110 != INF) {
        ans_val = n - tree.tree[1].min110 + 1;
    } else if (tree.tree[1].min101 != INF) {
        ans_val = 1;
    } else {
        ans_val = 0;
    }
    vans.push_back(ans_val);
    while(q--){
        int l,r;cin>>l>>r;
        tree.change(l,r);
        if (tree.tree[1].min110 != INF) {
            ans_val = n - tree.tree[1].min110 + 1;
        } else if (tree.tree[1].min101 != INF) {
            ans_val = 1;
        } else {
            ans_val = 0;
        }
        vans.push_back(ans_val);
    }
    int ans=0;
    for(int i=0;i<vans.size();i++){
        // cout<<vans[i]<<" \n"[i==vans.size()-1];
        ans=ans^((i+1)*vans[i]);
    }
    cout<<ans<<endl;
}


signed main()
{
    int T,c;cin>>c>>T;
    while(T--){
        solve4();
    }
    return 0;
}