Today Don Capone celebrates the anniversary of his mafia clan. On this occasion he invited the representatives of all the clans. \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{1000}) people came to the celebration. Each clan brought a holiday gift -- a case with a certain sum of money -- an integer number of thousands of dollars (\textbf{0} ≤ \textbf{D_i} ≤ \textbf{100}). Don Capone is very fastidious, that’s why he evaluates cases by their looks, and if he likes the case, he accepts the gift; otherwise he throws it away and dismisses the guest. Don’s assistant knows how much money brought every guest, but doesn’t know what cases Don will throw. At this point he wants to calculate how many variants of sums he could get in the end. The first line of the input file input.txt contains a number \textbf{T} -- the number of test cases in the file. \textbf{T} blocks of data follow. The first line of a block contains a single number \textbf{N}. The second line of a block contains N numbers, separated by spaces -- \textbf{D_1}, \textbf{D_2}, …, \textbf{D_N}. For each test case print a single line into standard output. The line must contain a single number -- the number of different sum values.