Одного разу хлопчик Петя вивчав позиційні системи числення. В них числа подаються у вигляді послідовності цифр
де b — основа системи числення, і 0 ≤ a_k < b. Петю розчаровувало, що так можна подавати лише невід'ємні числа, але він виявив, що існує негадвійкова система числення, у якій b=-2, a_k {0, 1}. У ній можна подавати усі цілі числа, наприклад, 1110_{-2} = -6. Вирішивши розвинути ідею, Петя придумав свою власну основу b, використовуючи яку можна отримувати ще більше різних чисел при a_k {0, 1}. Проте виконувати арифметичні операції у нестандартній системі виявилось не дуже легко. Допоможіть Петі написати калькулятор, який працює у його системі числення.
Перший рядок містить T (1 ≤ T ≤ 100) — кількість тестів. Наступні T рядків містять арифметичний вираз, який складається з відокрімлених пропусками першого аргументу, операції та другого аргументу. Обидва аргументи складаються з цифр '0' і '1' і мають довжину не більше 100. Операцією є один з символів '+', '-' чи '*'.
Для кожного тесту виведіть у окремому рядку одне число — результат арифметичної операції.