Мафия

Сегодня Дон Капоне празднует юбилей своего клана мафии. По этому случаю он пригласил представителей всех кланов. N (1 ≤ N ≤ 1000) человек пришло на торжество. Каждый клан принес праздничный подарок – кейс с некоторой суммой денег – целое число тысяч долларов (0 ≤ D_i ≤ 100). Дон Капоне очень привередливым, поэтому он оценивает кейсы по их виду, и если ему понравился кейс, он принимает подарок; в противном случае он отказывается от него и выгоняет гостя. Помощник Дона знает сколько денег принес каждый гость, но не знает от каких кейсов Дон откажется. Теперь он хочет вычислить сколько вариантов сумм, он мог бы получить в конце.

Технические условия

Первая строка входного файла содержит число T – количество тестов в файле. Далее следуют T блоков данные. Первая строка блока содержит одно число N, вторая строка – N чисел, разделенных пробелами – D₁, D₂, …, D_N.

Для каждого теста выведите одну строку в выходной файл. Строка должна содержать единственное число – количество различных значений сумм.

Информация о задаче

Лимит времени: 1 секунда
Лимит памяти: 64 MB
Баллы за пройденный тест: 1
Сложность: 21% 27/34

Пример

Пример входных данных

1
3
1 1 2

Пример выходных данных

← Сосед

Список задач