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 T (T ≤ 100) is given on the first line. Following T lines each have an expression in format A + B = C, where A, B, C (0 ≤ A + B, C ≤ 105) 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