LINQSOLV - Linear Equation Solver

no tags 

Given a system of linear equations, print the solution of that system.

Input

Input starts with a positive integer t<100 in a single line, then t testcases follow. Every testcase represents a linear system and starts with one line containing a positive integer n<21, the number of equations and also the number of variables of that system. Then n equations follow, each one in a single line.
An equation is written in schoolbook notation, i.e. variables noted by single small letters (english alphabet), no multiplication sign, factor 1 left out, no spaces in between. A variable or a value may occur zero or more times in an equation. All coefficients are integers with an absolute value less than 100, a single line won't be longer than 100 characters and will always contain a valid linear equation.

The following equations are considered to be valid:
a+b-c+b-2c-a=1       -x+5-9=-4x+y-8       c-c+t+1=0       y=z

The following equations are considered to be invalid:
4*a+b=6       6+-2x=99       c-c+t-t=0       4+9 = h

Output

For each testcase print all variables of the linear system in alphabetical order together with the associated value as an integer or a fraction in lowest terms respectively. Print a blank line between testcases. For exact notation see example below. All (interim) results will fit into 64-bit, if algorithm is implemented properly. You can assume that all linear systems have an unique solution.

Example

Input:
2
2
a+b=5
b-a=1
3
5u-5z+4=0
8k-3z=-2
9k-u=u
 
Output:
a=2
b=3

k=-4/55
u=-18/55
z=26/55


Added by:numerix
Date:2011-03-14
Time limit:0.5s
Source limit:10000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:own problem