Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

## ACM_0231 - HOLIDAY

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 ai 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 ai is a factor of 10, then remove 9/10 stones from each pile. Or more formally, a'i = ai / 10, where a'i is the new number of stones in the pile i.

Vasya’s goal is to empty all piles, so that ai = 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 ai, separated by space – number of stones in an individual pile (0 ≤ ai ≤ 109), 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

 № stdin stdout 1 321 6310 4 1315 201 45 248

 Ավելացրեց. Հրանտ Հովհաննիսյան Ամսաթիվ. 2014-10-08 Ժամանակի սահմանափակումը. 1s Ծրագրի տեքստի սահմանափակումը. 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Լեզուներ. Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE Աղբյուրը. East Sibirean QF 2014.H