Bạn được cho số nguyên không âm ban đầu \(S\) và số nguyên không âm đích \(E\), cả hai ở dạng biểu diễn nhị phân. Mục tiêu là biến đổi \(S\) thành \(E\) bằng hai thao tác:

1. Double: nhân giá trị hiện tại với \(2\).
2. NOT: lấy phủ định theo bit của giá trị hiện tại. Biểu diễn nhị phân trước thao tác không chứa số \(0\) thừa ở đầu; mọi số \(0\) thừa sinh ra sau thao tác cũng bị bỏ. Số \(0\) duy nhất trong biểu diễn của giá trị \(0\) là số \(0\) cần thiết.

Ví dụ, Double biến \(6\) thành \(12\), \(0\) thành \(0\), \(10\) thành \(20\). NOT biến \(0\) thành \(1\), \(1\) thành \(0\), \(3=11_2\) thành \(0\), \(14=1110_2\) thành \(1\), \(10=1010_2\) thành \(5=101_2\), và \(5=101_2\) thành \(2=10_2\). Ký hiệu \(X_2\) chỉ số có biểu diễn nhị phân \(X\).

Bạn có thể dùng hai thao tác bao nhiêu lần tùy ý theo bất kỳ thứ tự nào. Ví dụ:

Hãy tìm số thao tác ít nhất để hoàn tất biến đổi, hoặc cho biết điều đó là không thể.

Dữ liệu vào

Dòng đầu chứa số bộ dữ liệu \(T\). Mỗi bộ gồm một dòng chứa hai xâu \(S,E\), là biểu diễn nhị phân của số đầu và số đích.

Dữ liệu ra

Với mỗi bộ dữ liệu, in Case #x: y, trong đó \(x\) là số thứ tự (bắt đầu từ \(1\)). Nếu không thể biến \(S\) thành \(E\), \(y\) là IMPOSSIBLE; nếu có thể, \(y\) là số thao tác nhỏ nhất.

Ràng buộc

• \(1\le T\le100\).
• Mỗi ký tự của \(S\) và \(E\) là 0 hoặc 1.
• Ký tự đầu của \(S\) (tương tự của \(E\)) chỉ có thể là 0 khi xâu có độ dài \(1\).

Phân nhóm

• Test Set 1 (Visible Verdict): \(1\le|S|,|E|\le8\).
• Test Set 2 (Hidden Verdict): \(1\le|S|,|E|\le100\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

6
10001 111
1011 111
1010 1011
0 1
0 101
1101011 1101011

Case #1: 4
Case #2: 3
Case #3: 2
Case #4: 1
Case #5: IMPOSSIBLE
Case #6: 0

Nguồn

Google Code Jam 2021, Vòng 1C, bài Double or NOTing.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.