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

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

3
2
1 6
3
10 4 1
3
15 201 45
2
4
8

Ավելացրեց.Հրանտ Հովհաննիսյան
Ամսաթիվ.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

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.