Universal Studios Theme Parks announced a new game named _The Crazy Jumper_, that is targeted problem solving fans.
In this game, there are n large boxes numbered from 1 to n from left to right, such that the ith box (1 < i ≤ n) is located to the right of the (i - 1)th box. Each box has a color, such that ci is the color of the ith box.
The goal of the game is to reach the nth box starting from the 1st box, by jumping between the boxes. The player can do one of the following jumps:
Ziad will be the first one to play the game, but he is not sure whether the game is amusing or not, so he wants to finish it with the minimum number of jumps. Can you help Ziad by telling him what is the minimum number of required jumps to reach the nth box stating from the 1st box?
The first line contains an integer T, where T is the number of test cases.
The first line of each test case contains an integer n (1 ≤ n ≤ 2 × 105), where n is the number of the boxes in the game.
The second line of each test case contains n integers c1, c2, ..., cn (1 ≤ ci ≤ 2 × 105), where ci is the color of the ith box.
For each test case, print a single line containing the minimum number of required jumps to reach the nth box starting from the 1st box.
As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use _scanf/printf_ instead of _cin/cout_ in C++, prefer to use _BufferedReader/PrintWriter_ instead of _Scanner/System.out_ in Java.
## Input
The first line contains an integer T, where T is the number of test cases.The first line of each test case contains an integer n (1 ≤ n ≤ 2 × 105), where n is the number of the boxes in the game.The second line of each test case contains n integers c1, c2, ..., cn (1 ≤ ci ≤ 2 × 105), where ci is the color of the ith box.
## Output
For each test case, print a single line containing the minimum number of required jumps to reach the nth box starting from the 1st box.
[samples]
## Note
As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use _scanf/printf_ instead of _cin/cout_ in C++, prefer to use _BufferedReader/PrintWriter_ instead of _Scanner/System.out_ in Java.
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case $ k \in \{1, \dots, T\} $:
- Let $ n_k \in \mathbb{Z} $ denote the number of boxes, with $ 1 \leq n_k \leq 2 \times 10^5 $.
- Let $ C_k = (c_{k,1}, c_{k,2}, \dots, c_{k,n_k}) $ be a sequence of colors, where $ c_{k,i} \in \mathbb{Z} $ and $ 1 \leq c_{k,i} \leq 2 \times 10^5 $, representing the color of the $ i $-th box.
**Constraints**
1. $ 1 \leq T \leq \text{large (implied by constraints)} $
2. For each test case $ k $:
- $ 1 \leq n_k \leq 2 \times 10^5 $
- $ 1 \leq c_{k,i} \leq 2 \times 10^5 $ for all $ i \in \{1, \dots, n_k\} $
**Objective**
For each test case $ k $, find the minimum number of jumps to reach box $ n_k $ starting from box $ 1 $, where from box $ i $, a jump is allowed to:
- Box $ i+1 $ (next adjacent box), or
- Any box $ j > i $ such that $ c_{k,j} = c_{k,i} $ (same color jump).
Compute $ d_k $, the shortest path length (number of jumps) from box $ 1 $ to box $ n_k $ in the graph defined by these moves.