LINQSOLV - Linear Equation Solver
Given a system of linear equations, print the solution of that system.
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
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.
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