#include<bits/stdc++.h>

using namespace std;

const int maxn = (int)1.01e5;
const int maxq = (int)1.01e5;
const int maxc = (int)1.01e6;

struct LIS
{
    struct node
    {
        int v;
        node*next;
    };
    node*f;
    unsigned int size_;
    LIS():f(0), size_(0u) {};
    unsigned int size()
    {
        return size_;
    };
    int front()
    {
        return f->v;
    };
    void pop()
    {
        node*s = f;
        f = f->next;
        delete s;
        size_--;
    };
    void push(const int&v)
    {
        node*new_node = new node;
        new_node->v = v;
        new_node->next = f;
        f = new_node;
        size_++;
    };
    void clear()
    {
        f = (node*)0;
        size_ = 0u;
    }
} F[maxc];

int C[maxc];
int A[maxn];
int N, Q;

int sum[maxn];
bool orzyjq[maxn];

int lowbit(const int&a)
{
    return a&(-a);
}

void add(int o, const int&v)
{
    while(o <= N)
    {
        sum[o] += v;
        o += lowbit(o);
    }
}

int querysum(int o)
{
    int ans = 0;
    while(o > 0)
    {
        ans += sum[o];
        o -= lowbit(o);
    }
    return ans;
}

void solve()
{
    scanf("%d%d", &N, &Q);
    for(int i = 1; i <= 1000000; ++i) F[i].clear();
    for(int i = 1; i <= 1000000; ++i) C[i] = i;
    for(int i = 1; i <= N; ++i) sum[i] = 0;

    for(int i = 1; i <= N; ++i)
    {
        scanf("%d", &A[i]);
        F[C[A[i]]].push(i);
        if(orzyjq[i] = (A[i] != A[i-1])) add(i, 1);
    }

    for(int t = 1; t <= Q; ++t)
    {
        int op, x, y;
        scanf("%d%d%d", &op, &x, &y);
        if(op == 1)
        {
            if(x == y) continue;
            if(F[C[x]].size() <= F[C[y]].size())
            {
                while(F[C[x]].size() > 0u)
                {
                    const int o = F[C[x]].front();
                    F[C[x]].pop();
                    F[C[y]].push(o);
                    A[o] = C[y];
                    if(A[o] == A[o-1] && orzyjq[o])
                    {
                        add(o, -1);
                        orzyjq[o] = false;
                    }
                    if(A[o] == A[o+1] && orzyjq[o+1])
                    {
                        add(o+1, -1);
                        orzyjq[o+1] = false;
                    }
                }
            }
            else
            {
                while(F[C[y]].size() > 0u)
                {
                    const int o = F[C[y]].front();
                    F[C[y]].pop();
                    F[C[x]].push(o);
                    A[o] = C[x];
                    if(A[o] == A[o-1] && orzyjq[o])
                    {
                        add(o, -1);
                        orzyjq[o] = false;
                    }
                    if(A[o] == A[o+1] && orzyjq[o+1])
                    {
                        add(o+1, -1);
                        orzyjq[o+1] = false;
                    }
                }
                swap(C[x], C[y]);
            }
        }
        else
        {
            printf("%d\n", querysum(y)-querysum(x)+1);
        }
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--) solve();
    return 0;
}