Марта грає в гру з числом, записаним на дошці у двійковій системі числення без провідних нулів. Спочатку на дошці записано додатне число .
За один хід Марта виконує дві дії в такому порядку:
Стирає з запису будь-яку кількість нулів (можливо, жодного) і дописує будь-яку кількість нулів (можливо, жодного) у будь-які місця запису так, щоб він не починався з нуля. Одиниці стирати чи дописувати не можна.
Збільшує записане число на і записує результат замість нього, знову у двійковій системі числення без провідних нулів.
Марта виграє, якщо після одного з її ходів на дошці буде записано додатне число . Якщо n = m, вона виграє одразу, не зробивши жодного ходу. Знайдіть найменшу кількість ходів, за яку Марта може виграти, або повідомте, що виграти неможливо.
Перший рядок містить одне ціле число (1 \le t \le 1000) — кількість тестових випадків.
Кожен з наступних рядків містить два додатні числа і (1 \le n, m), записані у двійковій системі числення без провідних нулів і розділені пробілом.
Гарантується, що 1 \le |n|, |m| \le 1000, де — кількість цифр у двійковому записі числа .
Для кожного тестового випадку виведіть в окремому рядку одне ціле число — найменшу кількість ходів, або , якщо виграти неможливо.
Приклад 1
У першому тестовому випадку n = 6 = \texttt{110}, m = 14 = \texttt{1110}. Марта може виграти за два ходи:
Хід 1: Марта дописує нуль у кінець, \texttt{110} \to \texttt{1100} = 12, і збільшує число: 13 = \texttt{1101}.
Хід 2: Марта нічого не стирає й не дописує і збільшує число: 14 = \texttt{1110}.
У третьому тестовому випадку m = 1 отримати неможливо.
У четвертому тестовому випадку n = m, тож Марта виграє одразу.