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

Первая строка входного файла содержит число T - количество тестов в файле. Далее следуют T блоков данные. Первая строка блока содержит одно число N, вторая строка - N чисел, разделенных пробелами - D1, D2, …, DN.

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