AMR10D  Soccer Teams
My kid's favorite subject is math, as you know by now. He is learning division now, and his teacher has taught him about even numbers being divisible by 2, numbers whose digits add up to a multiple of 3 being exactly divisible by 3 etc.
He was familiar with division by 11 during selection for soccer teams on his playground, and was wondering whether there was any easy rule to see if a number was divisible by 11. For example, he wondered, if he arranged a number of digits 09 in a row to form a number, which ones would be divisible by 11?
He decided to start off with d[1] 1's, d[2] 2's ..., d[9] 9's, and seeing what is the minimum factor of 11 that he could get by using all these digits, together with any number of 0's. Please help him figure out how many digits there are in this minimum factor. If he will not be able to form a multiple of 11 in this way, print 1.
INPUT
The first line will contain the number of test cases T. T lines follow one corresponding to each test case.
Each line has 9 integers d[1] d[2] .... d[9].
OUTPUT
Output T lines one corresponding to each test case. The ith line should contain the required answer for the corresponding test case.
CONSTRAINTS
1 <= T <= 100
1 <= d[1] + ... + d[9] <= 100
SAMPLE INPUT
2
2 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 1
SAMPLE OUTPUT
2
3
EXPLANATION
For the first case, the number 11 can be formed which has 2 digits.
For the second case, number 209 can be formed which is divisible by 11 and has 3 digits.
hide comments
enigmus:
20161008 09:27:05
Worst case complexity of my solution is at most O(n^2*logn) maybe even a little bit better.


Anurag yadav:
20150909 08:23:48
Last edit: 20150909 08:27:57 

Aman Kumar:
20120307 18:45:43
awesome question ! :) 
Added by:  Varun Jalan 
Date:  20101213 
Time limit:  0.438s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  ICPC Asia regionals, Amritapuri 2010 