SPOJ in Gyumri

   During long school holidays a smart young boy Vasya plays the following game. Initially, he is given N piles of stones, each of them containing a_i stones. In one turn he can do exactly one of the following actions:

• Remove from 1 to 9 stones from any single pile (of course, if there are enough stones there).

• Reduce total number of stones tenfold using the following rule: if the number of stones in each individual pile a_i is a factor of 10, then remove 9/10 stones from each pile. Or more formally, a'_i = a_i / 10, where a'_i is the new number of stones in the pile i.

   Vasya’s goal is to empty all piles, so that a_i = 0, using minimum number of turns R. Please help him to calculate this number R of an optimal strategy.

Input data

   First line of the input contains a natural number T – the number of test cases. Then T test cases follow (T ≤ 210).

   Each test case contains one or two lines. First line contains integer number N – number of piles (0 ≤ N ≤ 100). If N > 0 then second line contains N integer numbers a_i, separated by space – number of stones in an individual pile (0 ≤ a_i ≤ 10⁹), otherwise, there is no second line.

Output data

   For every test case on a separate line print the number R – the minimum number of turns that Vasya has to make in order to empty all piles, assuming he plays optimally.

Examples