Sayı Oyunu#13074

Sayı Oyunu

1 saniye
256 megabayt

Marta, tahtaya ikili sistemde baştaki sıfırlar olmadan yazılmış bir sayıyla oyun oynuyor. Başlangıçta tahtada pozitif bir sayısı yazılıdır.

Bir hamlede Marta aşağıdaki sırayla iki işlem yapar:

  1. Yazılıştan istediği kadar sıfırı (hiç silmeyebilir) siler ve yazılışın istediği yerlerine istediği kadar sıfır (hiç eklemeyebilir) ekler; öyle ki yazılış sıfırla başlamasın. Birleri silmek veya eklemek yasaktır.

  2. Yazılı sayıyı artırır ve sonucu onun yerine, yine ikili sistemde baştaki sıfırlar olmadan yazar.

Marta, hamlelerinden birinden sonra tahtada pozitif sayısı yazılı olursa kazanır. Eğer n = m ise, tek bir hamle bile yapmadan hemen kazanır. Marta'nın kazanabileceği en az hamle sayısını bulun veya kazanmanın imkânsız olduğunu bildirin.

Giriş

İlk satırda bir tam sayı (1 \le t \le 1000) — test durumlarının sayısı verilir.

Sonraki satırın her biri, ikili sistemde baştaki sıfırlar olmadan yazılmış ve bir boşlukla ayrılmış iki pozitif ve (1 \le n, m) sayısını içerir.

1 \le |n|, |m| \le 1000 olduğu garanti edilir; burada , sayısının ikili yazılışındaki basamak sayısıdır.

Çıktı

Her test durumu için ayrı bir satırda tek bir tam sayı — en az hamle sayısını, kazanmak imkânsızsa yazdırın.

Örnekler

Örnek 1

Loading
Loading

Not

Birinci test durumunda n = 6 = \texttt{110}, m = 14 = \texttt{1110}. Marta iki hamlede kazanabilir:

  • Hamle 1: Marta sona bir sıfır ekler, \texttt{110} \to \texttt{1100} = 12, ve sayıyı artırır: 13 = \texttt{1101}.

  • Hamle 2: Marta hiçbir şey silmez ve eklemez, sayıyı artırır: 14 = \texttt{1110}.

Üçüncü test durumunda m = 1 elde etmek imkânsızdır.

Dördüncü test durumunda n = m olduğundan Marta hemen kazanır.