Калькулятор#3187
Колись Петя вивчав позиційні системи числення. У таких системах числа записуються у вигляді послідовності цифр:
Тут — основа системи числення, а 0 \leq a_{k} < b. Петя засмутився, що таким способом можна записати лише невід'ємні числа. Проте він з'ясував, що існують системи числення з від'ємною основою, наприклад, негабінарна система, де b = -2 і a_{k} \in \{0, 1\}. У такій системі можна записати всі цілі числа; наприклад, 1110_{-2} = -6. Розвиваючи цю ідею, Петя придумав власну систему з основою , яка дозволяє подати ще більше чисел, використовуючи a_{k} \in \{0, 1\}. Однак виконувати арифметичні операції у цій нестандартній системі виявилось досить складно. Допоможіть Петі реалізувати калькулятор для його системи числення.
У першому рядку задано число (1 \leq T \leq 100) — кількість тестів. У наступних рядках міститься по одному арифметичному виразу, який складається з першого операнда, операції та другого операнда, розділених пробілами. Обидва операнди містять тільки цифри '0' та '1' і не перевищують символів у довжину. Операцією є одна з '+', '-' або '*'.
Для кожного тесту виведіть одне число — результат виконання вказаної арифметичної операції.
Приклад 1