Send More Money

Last night, I was reading a novel by Dr. Humayun Azad (Renowned writer of Bangladesh, Died August 11, 2004 in Munich, Germany. He was there to join in a conference of the writers, arranged by PEN International). Suddenly my younger brother Roni came to me and asked for that book. I was just finished half of the book and the story was so interesting that I didn’t want to give it away then. I told him, “Ok, I’ll give you the book when you can solve a puzzle”. I knew he was very interested in solving mathematical problems so this can be a good trick to stick him with that puzzle for few hours and in the mean time I’d finish the book! He says, “Hmm I agree, then explain me the puzzle”. I said, “First tell me the result of a simple problem, what’ll be the answer of this summation?” 53+32=? He said, “Its very easy, 5 3 + 3 2 = 8 5”. “Correct! Now if I replace this summation with A B + B C = D A, can you tell me the numbers replaced by the characters?” Hesays,“Sure! A=5,B=3,C=2andD=8”. “Ok, now if I give you (A B + B C = D A) you have to figure out, (5 3 + 3 2 = 8 5)” He seemed little confused and asked, “Do you promise to give me that book if I can solve the puzzle?” I was sure of his failure and said, “I promise!” I gave him the following puzzle: SEND +MORE MONEY I was just finished two third of the book and suddenly hear his “Eureka!” He came to me dancing and showed me the following result: 9567 +1085 10662 I’d nothing to do but give him the book! Problem constraints • Each digit in the original summation was replaced by exactly one uppercase letter.

2/2 • There is a one to one relationship between digits and letters. That means: – No different digits were replaced by the same letter. – No same digits were replaced by different letters. • The original summation contained no leading zeros in the numbers (although the value 0 itself was allowed). You are given the words after the replacement. Can you get the original summation back? Input The first line of the input contains the number of test cases T (T ≤ 10). For each test case, first I’ll give you n (2 < n < 6) the number of words in one line and then those n words one after another separated by a space in a line. Here last word (n-th) is the result of the summation and other (n − 1) words are the summands. All words have between 1 and 10 uppercase letters. Output You have to figure out the numbers replaced by the letters. For each test case, print one line containing the replacement results for all used letters, sorted by alphabetic order like in the sample IO. Separate the results for different letters by one space character. You can assume, there is always exactly one solution. Sample Input 2 3 SEND MORE MONEY 3 CROSS ROADS DANGER Sample Output D=7 E=5 M=1 N=6 O=0 R=8 S=9 Y=2 A=5 C=9 D=1 E=4 G=7 N=8 O=2 R=6 S=3