SOLVE

LATER

Sanket and Laptops

Problem

Editorial

Analytics

As Sanket has become **Red Coder** now, so he wants to participate in as many contests as possible. Sanket owns **N laptops**, and he takes parts in the contest using each laptop so he can make submission for each problems as fast as possible (He is the Top Coder after all!).

But many of his friends are jealous of him. So they decided to challenge him. They asked him to assign a number to each of his laptop.
After that, they told Sanket that he can use the laptops in such a manner that **no two contest have the same sum when the numbers on the laptops used in that contests are added**.

Now, Sanket want to take part in as many contests as possible, but as he is too busy with his preparations for ACM-ICPC, he asks for your help. Determine the **maximum number of contests** he can participate in, keeping in mind the challenge given by his friends.

**Note :** Sanket can take part in a contest even if he does not use a laptop.

*Input:*

First line contains **t**, the number of test cases.

Each test case consists of 2 lines: the first one contains **N** (the number of Laptops that Sanket has) and the second line contains **N** space separated numbers assigned by Sanket to his Laptops denoted by **a[i]**.

*Output:*

For each test case you need to print a **single integer denoting the maximum number of contests** that Sanket would be able to participate in.

*Constraints:*

1<=t<=20

1<=N<=20

1<=a[i]<=100

Explanation

In the given test case t = 1.

We have laptops numbered 1,2 and 3.

So, all the different possibilities are:

{} - Sum=0

{1} - Sum=1

{2} - Sum=2

{3} - Sum=3

{1,2} - Sum=3

{1,3} - Sum=4

{2,3} - Sum=5

{1,2,3} - Sum=6

So, we see that **7** different sums are possible (3 is counted **only once**) and so output is 7.

Time Limit:
2.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Marking Scheme:
Marks are awarded when all the testcases pass.

Allowed Languages:
C,
C++,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
JavaScript(Rhino),
JavaScript(Node.js),
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala,
Scala 2.11.8,
Swift,
Visual Basic

Initializing Code Editor...

{"f377680": "/pagelets/problems-hint/algorithm/the-laptops/", "f37769b": "/pagelets/recommended-problems/algorithm/the-laptops/", "f37762d": "/pagelets/suggested-problems/algorithm/the-laptops/", "f3775f7": "/pagelets/show-submission/algorithm/the-laptops/", "f377658": "/pagelets/problem-author-tester/algorithm/the-laptops/"}

{}

realtime.hackerearth.com

80

3c2e9ef0a5b4682898a79978ab0c7197fc8dc7d2

58a29e5cae2309f04b28

/realtime/pusher/auth/