Exact Change

Interview

Time limit1sMemory limit1024 MB

Summary

Given package values in cents, find the smallest positive amount that no subset of the packages can sum to exactly.

Level: Medium4 of 10
Topics: Greedy, Sorting
Solved: No attempts yet

Problem

Whenever the UCF Programming Team travels to World Finals, Glenn likes having the exact amount of money needed for any purchase, so that he does not have to count or receive change. Most countries do not have many coin denominations, so Glenn makes "packages" of money, each with a fixed amount in cents. Glenn wants to know the smallest amount in cents that he cannot pay exactly using some combination of his packages.

Given a list of positive integers, find the smallest integer that cannot be written as the sum of some subset of the integers in the list.

Input

The first line contains a single integer $n$ ( $1 < n \le 100$ ), the number of package sets to evaluate. Each of the $n$ sets follows. The first line of each set contains a single integer $c$ ( $1 \le c < 31$ ), the number of different packages. The next line contains exactly $c$ positive integers separated by single spaces, the value of each package in cents. The sum of these $c$ integers does not exceed $10^9$ . Package values need not be distinct, so several packages may have the same value.

Output

For each set, first print "Set #i: " where $i$ is the set number starting at 1. Then print a single positive integer, the smallest value that cannot be represented as a sum of a subset of the packages. A package can be used at most once, but if $m$ packages share the same value, up to $m$ of them can be used in one subset. Leave a blank line after the output for each test case.

Examples1

Example 1

Input

3
6
12 8 1 2 4 100
3
1 2 3
6
3 1 3 2 3 3

Expected output

Set #1: 28

Set #2: 7

Set #3: 16