A DP Problem

Time limit1sMemory limit128 MB

Summary

Parse each linear equation without parentheses, solve for x, and report the floored solution or whether it is impossible or an identity.

Level: Easy3 of 10
Topics: String, Implementation, Math
Solved: No attempts yet

Problem

In this problem you must solve a very simple linear equation that has no parentheses and a single variable $x$ . An example of such an equation is:

2x-4+5x+300=98x

A general equation contains a = character with one expression on each side. Each expression is one or more terms combined by the + or - operator. Unary + or - operators are not allowed. Each term is either a single integer, an integer followed by the lower-case letter x, or the single character x (which is equivalent to 1x).

Write a program that finds the value of $x$ satisfying the equation. Note that the equation may have no solution or infinitely many solutions; your program must detect these cases as well.

Input

The first number $t$ ( $1 \le t \le 10$ ) is the number of test cases, followed by $t$ lines, each containing one equation. Each line is at most 255 characters long. The equations contain no blank characters and the variable is always the lower-case letter x. The coefficients are integers in the range $0$ to $1000$ inclusive.

Output

For each test case, print one line containing the solution of the equation. If $s$ is the solution, the output line must contain $\lfloor s \rfloor$ (the floor of $s$ , i.e., the largest integer less than or equal to $s$ ). Print IMPOSSIBLE if the equation has no solution, or IDENTITY if it has infinitely many solutions. The output is case-sensitive.

Examples3

Example 1
Input
```
2
2x-4+5x+300=98x
x+2=2+x
```
Expected output
```
3
IDENTITY
```

Example 2

Input

5
x=5
2x+3=0
x+1=x+2
2x=2x
1000x=1000

Expected output

5
-2
IMPOSSIBLE
IDENTITY
1

Example 3
Input
```
4
3x+1=0
x+5=0
x=0
7x=3
```
Expected output
```
-1
-5
0
0
```