__Problem:- __

__Problem:-__

Chef decided to teach some advanced recipes to junior chefs. On the very first day of their cooking sessions, to identify the cooking abilities of each junior chef, Chef instructed them to make their premier dishes. The junior chefs were very excited and they all went into the kitchen to cook their dishes.

Chef has a limited number of jars in the kitchen. The jars are magical ― if a chef that is cooking a dish requiring $\ufffd$ ingredients takes $\ufffd$ jars, each of these jars fills itself with one of the required ingredients, and after this chef finishes cooking and returns the jars to the kitchen, they empty themselves (and are ready for other chefs to take some or all of them). Of course, this means it is impossible to cook a dish requiring $\ufffd$ ingredients with less than $\ufffd$ jars.

Since Chef did not tell the junior chefs in which order they should prepare their dishes, they started picking up jars simultaneously and in the end, no junior chef was able to acquire enough jars to prepare their premier dish. Also, none of the junior chefs are willing to lend their jars to others. Chef was unable to handle the situation and decided to call off the cooking session for that day, so that he could get more jars and try it again later.

You know that there are $\ufffd$ junior chefs (numbered $1$ through $\ufffd$) and for each valid $\ufffd$, the number of ingredients required for the dish of the $\ufffd$-th chef is ${\ufffd}_{\ufffd}$. If there are $\ufffd$ jars, then formally, the following process happens:

- The junior chefs take some jars; let's denote the number of jars taken by the $\ufffd$-th chef by ${\ufffd}_{\ufffd}$. Any distribution of jars such that $0\le {\ufffd}_{\ufffd}$ for each valid $\ufffd$ and ${\sum}_{\ufffd=1}^{\ufffd}{\ufffd}_{\ufffd}=\ufffd$ is possible.
- At any time, if ${\ufffd}_{\ufffd}<{\ufffd}_{\ufffd}$ for each chef $\ufffd$ that has not prepared their dish yet, the cooking session is a failure.
- Otherwise, one of the chefs who have at least as many jars as the number of required ingredients prepares their dish and returns their jars to the kitchen.
- Whenever some jars are returned to the kitchen, they are immediately taken by some chefs that have not prepared their dishes yet (possibly all the jars by one chef).
- This process continues with chefs taking jars, cooking their dishes and returning jars, until no chef can cook their dish anymore or all chefs have cooked their dishes.
- When all junior chefs have successfully cooked their dishes, the cooking session ends successfully.

Chef wants to know the minimum number of magical jars that should be present in the kitchen initially so that the session would be successful regardless of how the junior chefs pick up the jars. Chef is a legendary cook, but he is not very good at mathematics, so he asks you to find that number.

### Input

- The first line of the input contains a single integer $\ufffd$ denoting the number of test cases. The description of $\ufffd$ test cases follows.
- The first line of each test case contains a single integer $\ufffd$.
- The second line contains $\ufffd$ space-separated integers ${\ufffd}_{1},{\ufffd}_{2},\dots ,{\ufffd}_{\ufffd}$.

### Output

For each test case, print a single line containing one integer ― the minimum required number of jars.

### Constraints

- $1\le \ufffd\le 1,000$
- $1\le \ufffd\le 1{0}^{5}$
- $1\le {\ufffd}_{\ufffd}\le 1{0}^{9}$ for each valid $\ufffd$
- the sum of $\ufffd$ over all test cases does not exceed $1{0}^{6}$

### Subtasks

Subtask #1 (100 points): original constraints

### Sample 1:

2 4 1 1 1 1 2 1 4

1 4

### Explanation:

Example case 1: One of the junior chefs always picks up the only jar, cooks their dish and returns the jar back to the kitchen. Then, another junior chef picks up that jar, cooks their dish and returns the jar. This procedure can be repeated by each junior chef so that they can cook their recipe.

**code(c++):-**

__Code(JAVA):-__

__Recommended Post ____:-__

__Recommended Post__

__:-__

__HCL Coding Questions:-__

__Capgemini Coding Questions:-__

__iMocha coding Questions:-__

__Tech Mahindra coding questions:-__

__Unthinkable Solutions coding questions:-__- Swap the adjacent characters of the string
- Double the vowel characters in the string
- Character with their frequency
- Program to find the closest value

__Must check this:-__

__Companies interview:-__- Swap adjacent characters
- Double the vowel characters
- Check valid parenthesis
- Print the characters with their frequencies
- Find closest value
- Word Count
- Program of CaesarCipher
- Program to find the perfect city
- Annual Day | Tech Mahindra coding question
- Find the number of pairs in the array whose sum is equal to a given target.

__Full C course:- __

__Key points:-__

- How to set limit in the floating value in python
- What is boolean data type
- How to print any character without using format specifier
- How to check that given number is power of 2 or not
- How to fix limit in double and floating numbers after dot (.) in c++
- How to print a double or floating point number in scientific notation and fixed notation
- How to take input a string in c
- How to reduce the execution time of program in c++.

__Cracking the coding interview:-__

__Array and string:-__

__Tree and graph:-__

__Hackerearth Problems:-__

- Very Cool numbers | Hacker earth solution
- Vowel Recognition | Hackerearth practice problem solution
- Birthday party | Hacker earth solution
- Most frequent | hacker earth problem solution
- program to find symetric difference of two sets
- cost of balloons | Hacker earth problem solution
- Chacha o chacha | hacker earth problem solution
- jadu and dna | hacker earth solution
- Bricks game | hacker earth problem
- Anti-Palindrome strings | hacker earth solution
- connected components in the graph | hacker earth data structure
- odd one out || hacker earth problem solution
- Minimum addition | Hackerearth Practice problem
- The magical mountain | Hackerearth Practice problem
- The first overtake | Hackerearth Practice problem

__Hackerrank Problems:-__- Playing With Characters | Hackerrank practice problem solution
- Sum and Difference of Two Numbers | hackerrank practice problem solution
- Functions in C | hackerrank practice problem solution
- Pointers in C | hackerrank practice problem solution
- Conditional Statements in C | Hackerrank practice problem solution
- For Loop in C | hackerrank practice problem solution
- Sum of Digits of a Five Digit Number | hackerrank practice problem solution
- 1D Arrays in C | hackerrank practice problem solution
- Array Reversal | hackerrank practice problem solution
- Printing Tokens | hackerrank practice problem solution
- Digit Frequency | hackerrank practice problem solution
- Calculate the Nth term | hackerrank practice problem solution

__Data structure:-__

- Program to find cycle in the graph
- Implementation of singly link list
- Implementation of queue by using link list
- Algorithm of quick sort
- stack by using link list
- program to find preorder post order and inorder of the binary search tree
- Minimum weight of spanning tree
- Preorder, inorder and post order traversal of the tree

__ MCQs:-__

## 0 Comments