---{"category_name":"school","problem_code":"SC31","problem_name":"Weapon Value","problemComponents":{"constraints":"","constraintsState":false,"subtasks":"","subtasksState":false,"inputFormat":"","inputFormatState":false,"outputFormat":"","outputFormatState":false,"sampleTestCases":{"0":{"id":1,"input":"1\r\n3\r\n1110001101\r\n1010101011\r\n0000000011","output":4,"explanation":"**Example case 1:** If the first person defeats the second person, weapons $1$, $3$, $7$ and $10$ are destroyed. Then, if the third person defeats the first person (who now has weapons $2$, $5$, $8$ and $9$), weapons $9$ are destroyed and the winner has weapons $2$, $5$, $8$ and $10$.","isDeleted":false}}},"video_editorial_url":"","languages_supported":{"0":"CPP14","1":"C","2":"JAVA","3":"PYTH 3.6","4":"PYTH","5":"PYP3","6":"CS2","7":"ADA","8":"PYPY","9":"TEXT","10":"PAS fpc","11":"NODEJS","12":"RUBY","13":"PHP","14":"GO","15":"HASK","16":"TCL","17":"PERL","18":"SCALA","19":"LUA","20":"kotlin","21":"BASH","22":"JS","23":"LISP sbcl","24":"rust","25":"PAS gpc","26":"BF","27":"CLOJ","28":"R","29":"D","30":"CAML","31":"FORT","32":"ASM","33":"swift","34":"FS","35":"WSPC","36":"LISP clisp","37":"SQL","38":"SCM guile","39":"PERL6","40":"ERL","41":"CLPS","42":"ICK","43":"NICE","44":"PRLG","45":"ICON","46":"COB","47":"SCM chicken","48":"PIKE","49":"SCM qobi","50":"ST","51":"NEM"},"max_timelimit":1,"source_sizelimit":50000,"problem_author":"invincibel","problem_tester":null,"date_added":"7-10-2019","tags":{"0":"challenge","1":"invincibel","2":"nov19","3":"watcher","4":"xor"},"problem_difficulty_level":"Simple","best_tag":"","editorial_url":"https://discuss.codechef.com/problems/SC31","time":{"view_start_date":1573464602,"submit_start_date":1573464602,"visible_start_date":1573464602,"end_date":1735669800},"is_direct_submittable":false,"problemDiscussURL":"https://discuss.codechef.com/search?q=SC31","is_proctored":false,"visitedContests":{},"layout":"problem"}---### Read problem statements in [Hindi](https://www.codechef.com/download/translated/NOV19/hindi/SC31.pdf), [Bengali](https://www.codechef.com/download/translated/NOV19/bengali/SC31.pdf), [Mandarin Chinese](https://www.codechef.com/download/translated/NOV19/mandarin/SC31.pdf), [Russian](https://www.codechef.com/download/translated/NOV19/russian/SC31.pdf), and [Vietnamese](https://www.codechef.com/download/translated/NOV19/vietnamese/SC31.pdf) as well.A competition with $N$ participants (numbered $1$ through $N$) is taking place in Chefland. There are $N-1$ rounds in the competition; in each round, two arbitrarily chosen contestants battle, one of them loses and drops out of the competition.There are $10$ types of weapons (numbered $1$ through $10$). You are given $N$ strings $S_1, S_2, \ldots, S_N$; for each valid $i$ and $j$, the $j$-th character of $S_i$ is '1' if the $i$-th contestant initially has a weapon of type $j$ or '0' otherwise. During each battle, for each type $j$ such that both contestants in this battle currently have weapons of type $j$, these weapons of both contestants are destroyed; after the battle, the winner collects all remaining (not destroyed) weapons of the loser. Note that each contestant may win or lose regardless of the weapons he/she has.Chef is feeling bored watching the contest, so he wants to find the maximum possible number of weapons the winner of the tournament could have after the last battle, regardless of which contestants fight in which battles or the results of the battles. Can you help him?### Input- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.- The first line of each test case contains a single integer $N$.- $N$ lines follow. For each valid $i$, the $i$-th of these lines contains a single string $S_i$.### OutputFor each test case, print a single line containing one integer ― the maximum number of weapons the winner could have.### Constraints- $1 \le T \le 10$- $1 \le N \le 10^5$- $|S_i| = 10$ for each valid $i$### Subtasks**Subtask #1 (30 points):** $1 \le N \le 10$**Subtask #2 (70 points):** original constraints### Example Input```13111000110110101010110000000011```### Example Output```4```### Explanation**Example case 1:** If the first person defeats the second person, weapons $1$, $3$, $7$ and $10$ are destroyed. Then, if the third person defeats the first person (who now has weapons $2$, $5$, $8$ and $9$), weapons $9$ are destroyed and the winner has weapons $2$, $5$, $8$ and $10$.<aside style='background: #f8f8f8;padding: 10px 15px;'><div>All submissions for this problem are available.</div></aside>