Once little Petya was learning positional numeral systems. Using such systems the numbers are represented as the sequence of digits \includegraphics{https://static.e-olymp.com/content/da/da82a99020a46229961fa5fac4fa96d7adc3a86b.jpg} \includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg} \includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg} where \textbf{b} is the base of the numeral system, and \textbf{0} ≤ \textbf{a_k} < \textbf{b}. Petya was dissapointed that one can represent only non-negative numbers this way. But then he found out that there are systems with negative base such as negabinary system in which \textbf{b=-2}, \textbf{a_k} \{\textbf{0}, \textbf{1}\}.One can represent any integer in this system for example \textbf{1110_\{-2\} = -6}. Moving the idea further Petya came up with his own base \textbf{b} using which he could represent even more numbers given \textbf{a_k} \{\textbf{0}, \textbf{1}\}. However performing arithmetic operations in this non-standard system turned to be rather difficult. Help Petya implement a calculator for his numeral system. \InputFile The first line of input is number \textbf{T} (\textbf{1} ≤ \textbf{T} ≤ \textbf{100}) --- the amount of test cases. Next \textbf{T} lines contain the description of arithmetic expression consisting of two operands and an opertaion separated with spaces. Both operands consist of one '\textbf{0}' and '\textbf{1}' digits and have the length of no more than \textbf{100}. Operation is one of '\textbf{+}', '\textbf{-}' or '\textbf{*}'. \OutputFile For each test case output a number which is the result of evaluating the given expression.