B  — Arithmetic

Time Limit: 1 sec
Memory Limit: 32 MB

Alice is really bad at arithmetic. Sometimes she can’t properly add two single-digit numbers without using a computer! It is quite embarrassing, so she comes up with silly explanations when someone spots an error. Last time, after writing 5 + 4 = 10, Alice said - "Hey, this is right in base 9!".

Since you know how to program, can you help Alice and check her last bunch of calculations for any mistakes she might have left? She considers expression "correct" if equality is satisfied for any positional numeral system with base B (1 ≤ B) (in base 1 character '1' is used as only possible digit).

INPUT

The number of expressions N (T ≤ 100) is given on the first line. Following N lines each have an expression in format A + B = C, where A, B, C (0 ≤ A + B, C ≤ 10⁵) are non-negative decimal integers.

OUTPUT

For each expression, output a single line with the smallest counting system base B in which expression is correct. In case there is no such base, output "0".

SAMPLE INPUT

4
155 + 102 = 301
1022 + 221 = 1303
6502 + 6800 = 11202
515 + 7 = 522

SAMPLE OUTPUT

6
4
0
10