Alice is inviting her friends to a party to eat cakes. However, each friend may not be at the same place, so everyone has to meet up at the same location first.

Alice has $$$n$$$ friends, where the $$$i$$$-th friend is at position $$$a_i$$$. To make everyone be at the same place, Alice has to make multiple group calls. Unfortunately, the signal is weak, and Alice can only call $$$2$$$ other people at a time.

Being a good person, Alice doesn't want her friends to walk too far. So, for each group call containing the $$$i$$$-th friend and the $$$j$$$-th friend, Alice will tell both of them to meet at some integer location between $$$\min(a_i, a_j)$$$ and $$$\max(a_i, a_j)$$$ inclusive. After that, both of them will move to that location so quickly that Alice cannot make any group call during their movement. Please note that Alice can call these friends again once they reach that location.

The party is starting soon, so Alice needs to make group calls fast. Help her find the minimum number of group calls she needs to make.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$2 \leq n \leq 100$$$) — the number of friends Alice has.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the locations of her friends.

Output

For each test case, output the minimum number of group calls she needs to make in order for all of her friends to be in the same location.

Note

In the first test case, the minimum number of group calls is 2. One way to make everyone at the same location is as follows:

Call the $$$1$$$-st and $$$4$$$-th friend and tell them to move to location $$$3$$$. Their locations are now $$$[3, 2, 3, 3, 5]$$$.
Call the $$$2$$$-nd and $$$5$$$-th friend and tell them to move to location $$$3$$$. Their locations are now $$$[3, 3, 3, 3, 3]$$$.

In the second test case, the minimum number of group calls is 2. One way to make everyone at the same location is as follows:

Call the $$$1$$$-st and $$$4$$$-th friend and tell them to move to location $$$1$$$. Their locations are now $$$[1, 1, 1, 1, 2]$$$.
Call the $$$4$$$-th and $$$5$$$-th friend and tell them to move to location $$$1$$$. Their locations are now $$$[1, 1, 1, 1, 1]$$$.

Convergence

Examples