A Problem on Sticks TREE2

 

A Problem on Sticks (TREE2)

On a sunny day, Akbar and Birbal were taking a leisurely walk in palace gardens. Suddenly, Akbar noticed a bunch of sticks on the ground and decided to test Birbal's wits.

There are  stick holders with negligible size (numbered through ) in a row on the ground. Akbar places all the sticks in them vertically; for each valid i, the initial height of the stick in the -th holder is . Birbal has a stick cutter and his task is to completely cut all these sticks, i.e. reduce the heights of all sticks to . He may perform zero or more operations; in each operation, he should do the following:

  • Choose an integer Hand to fix the cutter at the height above the ground.
  • The cutter moves from the -st to the -th stick holder. Whenever it encounters a stick whose current height is greater than , it cuts this stick down to height (i.e. for a stick with height >H, it removes its upper part with length ).
  • All the upper parts of sticks that are cut in one operation must have equal lengths. Otherwise, the operation may not be performed.

For example, if the heights of sticks are initially , then some valid values for  in the first operation are and ― the cutter cuts the upper parts of two sticks and their lengths are  and  respectively. H is an invalid choice because it would cut the upper parts of all three sticks with lengths , which are not all equal.

Akbar wants Birbal to completely cut all sticks in the minimum possible number of operations. If you want to be friends with Birbal, help him solve the problem.

Input

  • The first line of the input contains a single integer  denoting the number of test cases. The description of  test cases follows.
  • The first line of each test case contains a single integer .
  • The second line contains  space-separated integers 

Output

For each test case, print a single line containing one integer ― the minimum number of operations needed to completely cut all the sticks.

Constraints



  •  for each valid 

Subtasks

Subtask #1 (20 points): 

Subtask #2 (80 points): original constraints

Example Input

1
3
1 2 3

Example Output

3

Explanation

Example case 1: Birbal may perform the following three operations:

  • Fix the cutter at . The heights of the sticks after this operation are .
  • Fix the cutter at . The heights of the sticks after this operation are .
  • Fix the cutter at . After this operation, all sticks are completely cut.

Python Solution

t=int(input())
while t>0:
    t-=1
    n=int(input())
    s = [int(i) for i in input().split()]
    if 0 in s:
        print(len(set(s))-1)
    else :
        print(len(set(s)))
Newest
Previous
Next Post »

Please don’t SPAM ConversionConversion EmoticonEmoticon