Problem Description

Rausen loves cakes. One day, he bought $n$ cakes and the color of each cake is described as an integer in $\left[1,1000000\right]$. Rausen lines the cakes from left to right.

Before eating, rausen proceeds $q$ operations on cakes.

At one time point, rausen would replace all cakes of $x$ color with those of color $y$.

At another time point, rausen would calculate the number of segment colors in the interval$\left[x,y\right]$. A color segment is defined as an interval of one single color. For example,'1 4 4 1 1' involves 3 color segments.

Nevertheless, rausen finds that he cannot compile the statistics of color segments in the interval, which makes him weep like a helpless crybaby (bazinga). Please help rausen resolve the problem to placate him.

Input

There are multiple test cases. The first line of input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains 2 integers $n$,$q$.

In the following $q$ lines,each line contains 3 integers: $op\left(1\leq op\leq 2\right)$, $x$ and $y$ which describe one operation:

If $op=1$, then rausen is to proceed a substitution operation and this is when you replace cakes of color $x$ with those of color $y$.$x$ and $y$ satisfy $\left (1\leq x,y\leq 1000000 \right)$.

if $op=2$, then rausen is to proceed a counting operation and this is when you are required to input the color segments in the interval $\left[x,y\right]$.$x$ and $y$ satisfy $\left(1\leq x\leq y\leq n\right)$

$\left(1\leq T\leq 5 \right)$,$\left(1\leq n\leq {10}^{5} \right)$,$\left(1\leq q\leq {10}^{5} \right)$

Output

For every counting operation of each case, a single line contains one number as the answer.

1
5 3
1 4 4 10 1
2 1 5 
1 4 10
2 3 5

4
2