# Culinary Expert and the Orchard Puzzle

Easy
0.0% Acceptance

Our beloved culinary expert loves to whip up exquisite meals. This time around, the expert has set their sights on creating a unique dish just for you, which requires a collection of apples.

In the expert's private orchard, there are $N$ apple trees, each bearing a certain (non-zero) amount of apples. To concoct this special dish, the expert aims to harvest every apple from each tree.

The expert has a peculiar approach to gathering apples. Within a single minute, they can carry out the following actions:

• Select any group of trees where each tree in the group bears the same number of apples.
• From every tree in the group, pluck any number of apples, ensuring the number of apples remaining on the tree matches the count on any tree not included in the group.

If all trees end up with the same amount of apples remaining, the expert can remove all the remaining apples in just one minute.

Eager to not delay your experience, the culinary expert wishes to complete this task in the shortest time possible. Can you determine the minimal time required?

### Input

The first line of the input includes a single integer $T$ indicating the number of test cases, followed by $T$ individual test cases. The initial line of each test case contains a single integer $N$ representing the number of apple trees in the expert's orchard. The subsequent line of each test case lists $N$ space-separated integers denoting the count of apples on each tree.

### Output

For each of the $T$ test scenarios, output a single line - the shortest time to harvest all apples from all trees.

### Constraints

• 1 <= $T$ <= 10
• 1 <= $N$ <= 10^5
• 1 <= Number of apples on a tree <= 10^5

### Sample Test Cases (and explanation)

#### Case #1:

Input:

2
3
3 3 3
4
1 2 3 3

Output:

1
3

#### Explanation

• For test 1, the expert can select all the trees and harvest all the apples in 1 minute.

• For test 2, there are several strategies for the expert to harvest all of the apples in 3 minutes. Here's one approach:

• First minute: Choose the third and fourth trees. Harvest 1 apple from the third tree and 2 apples from the fourth tree.

• Second minute: Opt for the second and third tree. Harvest 1 apple from each tree.

• Third minute: Select all the trees and harvest the remaining apple from each tree.