BLUEEQ - Help Blue Mary Please! (Act I)

This morning Blue Mary wrote some equations on a piece of paper and left it on her desk. After solving some problems in SPOJ, she found that her classmate H.L. replaced all characters on the paper with some other ones. H.L. told her he replaced the same characters with the same ones, and different characters with different ones because of his goodness. Now Mary needs your help to get the original equations back.

In Mary's equations, only 13 characters appear: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, *, =. There is one and only one "=" in each equation. In H.L.'s equations, only 13 Latin letters appear: a, b, c, d, e, f, g, h, i, j, k, l, m. All the equations are correct in decimal notation.

For example. If Mary wrote down 2+29=31, H.L. replaced 2 with i, + with l, 9 with k, = with e, 3 with m and 1 with a, we got ilikema.

Input

The first line contains a single integer t. t blocks follow.

To every block, the first line contains a single integer n (1 <= n <= 1000). n lines follow, each contains a string whose length is more than 4 and less than 12.The string contains only a-m and doesn't contain any whitespace.

At least 90% of test cases satisfy that n <= 5.

At least 80% of test cases satisfy that n <= 2.

In at least 70% of test cases, there are at most 5 different characters in all the equations.

Output

If there doesn't exist n equations that can be translated to H.L.'s equations, print a line contains the word noway. Otherwise you should output all the corresponding relations that can be fixed in lexicographic order, see the example.

Example

Input
1
2
abcdec
cdefe

Output
a6
b*
d=
f+

hint

The two strings can be translated to the following equations possibly:

  • 6*2=12     2=1+1
  • 6*4=24     4=2+2
  • 6*8=48     8=4+4

So the corresponding relations above can be fixed, others can not.


Added by:Fudan University Problem Setters
Date:2007-04-01
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO
Resource:Chinese National Olympiad in Informatics 2000,Day 2; translated by Blue Mary

hide comments
2013-05-15 16:55:54 Niklas Baumstark
Thank you Nenad :) Any comments on the leading zeroes part?
2013-05-14 07:58:05 Nenad Bo¾idareviæ
I don't think anybody reads these, but let's give it a shot... [Got AC, here are my conclusions]

How do we format the output for multiple test cases? [One after another]

What should we output when there are multiple solutions, but no character can be fixed? Noway, empty line, or nothing (as if the test case didn't exist)? [Nothing, as if it didn't exist]

Can there be operators on both sides of the equation? [Yes]

Last edit: 2013-05-14 22:22:43
2011-06-29 17:38:57 Hagen von Eitzen
Is '+' also allowed as unary sign?
I.e.: Is "2*2=+4" a valid equation?

RE: '+' or '-' can not be used as unary operations.

Last edit: 2011-08-16 02:37:00
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.