Числова гра#13074

Числова гра

1 секунда
256 мегабайтів

Марта грає в гру з числом, записаним на дошці у двійковій системі числення без провідних нулів. Спочатку на дошці записано додатне число .

За один хід Марта виконує дві дії в такому порядку:

  1. Стирає з запису будь-яку кількість нулів (можливо, жодного) і дописує будь-яку кількість нулів (можливо, жодного) у будь-які місця запису так, щоб він не починався з нуля. Одиниці стирати чи дописувати не можна.

  2. Збільшує записане число на і записує результат замість нього, знову у двійковій системі числення без провідних нулів.

Марта виграє, якщо після одного з її ходів на дошці буде записано додатне число . Якщо n = m, вона виграє одразу, не зробивши жодного ходу. Знайдіть найменшу кількість ходів, за яку Марта може виграти, або повідомте, що виграти неможливо.

Вхідні дані

Перший рядок містить одне ціле число (1 \le t \le 1000) — кількість тестових випадків.

Кожен з наступних рядків містить два додатні числа і (1 \le n, m), записані у двійковій системі числення без провідних нулів і розділені пробілом.

Гарантується, що 1 \le |n|, |m| \le 1000, де — кількість цифр у двійковому записі числа .

Вихідні дані

Для кожного тестового випадку виведіть в окремому рядку одне ціле число — найменшу кількість ходів, або , якщо виграти неможливо.

Приклади

Приклад 1

Loading
Loading

Примітка

У першому тестовому випадку 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, тож Марта виграє одразу.