34626번 - Increase or Smash 다국어

문제

Geumjae has an array $a$ consisting of $n$ zeros. His goal is to transform it into a given target array using a minimum number of operations.

He can perform the following two types of operations any number of times, in any order:

1. Increase: Choose any positive integer $x$. Increase all elements of the array $a$ by $x$. In other words, he chooses a positive integer $x,ドル and for each $i$ (1ドル \le i \le n$), he replaces $a_i$ with $a_i + x$.
2. Smash: Set some elements (possibly none or all) of the array $a$ to 0ドル$. In other words, for each $i$ (1ドル \le i \le n$), he either replaces $a_i$ with 0ドル$ or leaves it as before.

Given the final target state of the array $a,ドル find the minimum total number of operations (both Increase and Smash) Geumjae needs to perform.

It can be shown that for any given final array, a sequence of operations always exists.

입력

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

The first line contains a single integer $n$ (1ドル \le n \le 100$) --- the number of elements in the array $a$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ (1ドル \le a_i \le 100$) --- the elements of the target array $a$.

출력

For each test case, output a single integer --- the minimum number of operations required.

제한

노트

Explanation of the first test case:

The target array is $[1, 1, 3]$. A possible sequence of 3 operations (which is the minimum) is:

• Initially, the array is $[0, 0, 0]$. After an Increase operation with $x = 2,ドル the array becomes $[2, 2, 2]$.
• Next, after a Smash operation on the first two elements, the array becomes $[0, 0, 2]$.
• Finally, after an Increase operation with $x = 1,ドル the array becomes $[1, 1, 3]$.

We used 2ドル$ Increase operations and 1ドル$ Smash operation for a total of 3ドル$ operations.

Explanation of the second test case:

The target array is $[100]$. A single Increase operation with $x = 100$ gives the target array.