I. The Crazy Jumper
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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:

  1. Jump one box to the right.
  2. If the player stands at a box of color x, he/she can jump to the closest box of color x that is to the right of him, if such box exist.

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?

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.

Example
Input
3
6
9 2 4 7 1 5
5
1 2 1 1 4
6
1 2 3 1 3 2
Output
5
3
2
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.