1240 - Yet Another A+B Problem

Time Limit : 10 Second

Memory Limit : 128 MB

Submission: 139

Solved: 34

Description
We all have come across A+B Problem many times. This time, you are to solve another A+B Problem. An addition rebus is a puzzle where you get an addition equation, like "ABC+CBA=BDB". And you need to replace each letter with a digit (from 0 through 9) in such a way that:

  • Equal letters are replaced with equal digits.

  • Different letters are replaced with different digits.

  • None of the resulting numbers starts with 0, unless the entire number is just 0.

  • The resulting equation holds.


Now you are given N addition rebuses, and you are to tell me the maximum number X that there exists a map from each letter to a digit satisfying first X equations but there exists none satisfying first X+1 equations. If there exists a sequence satisfying all the given equations, then number X should be the number of all the equations given. And if there exists none sequence satisfying the first equation, then number X should be 0.
Input
The input consists of multiple test cases. The first line of input contains an integer T (T <= 10), which is the number of test cases.

The first line of each test case contains the number N (N <= 10), indicating the total number of equations.

The next N line each contains an addition rebus described above. Equations are consisted of numbers (represented by capital letters) and operators ("+" and "="). You can assume that there exists no more than 10 different letters in each test case and the length of each number is a positive integer less or equal to 20.
Output
For each test case, your program should output one line containing the maximum number X as we described above.
sample input
2
2
AAA+BBB=CCC
AAA+CCC=DDD
3
ABC+CBA=DDD
AAA+BBB=EEE
ABA+CBC=EEE
sample output
2
2
hint
source
<a href="http://aifreedom.com/">Ai.Freedom</a>
© 2015 HUST ACMICPC TEAM. All Right Reserved.