Đảo ngược nhị phân của tổng

Cho hai xâu nhị phân $x$ và $y$, là biểu diễn nhị phân của hai số nguyên (gọi là $f(x)$ và $f(y)$).

Bạn có thể chọn một số nguyên $k\ge 0$ bất kỳ, tính giá trị

$$s_k=f(x)+f(y)·2^k$$

rồi viết biểu diễn nhị phân của $s_k$ theo thứ tự đảo ngược (ký hiệu là ${\text{rev}}_k$).

Ví dụ, với $x=1010$ và $y=11$, nếu chọn $k=1$ thì $2^1={10}_2$, nên $s_k={1010}_2+{11}_2·{10}_2={10000}_2$ và ${\text{rev}}_k=00001$.

Với $x$ và $y$ cho trước, hãy tìm $k$ sao cho ${\text{rev}}_k$ là nhỏ nhất theo thứ tự từ điển.

Dữ liệu đảm bảo với ràng buộc đã cho, luôn tồn tại $k$ hữu hạn thoả mãn.

So sánh theo thứ tự từ điển: so sánh từng ký tự từ trái sang phải; tại vị trí đầu tiên khác nhau, xâu có ký tự nhỏ hơn (0 < 1) là xâu nhỏ hơn. Nếu một xâu là tiền tố của xâu kia thì xâu ngắn hơn là xâu nhỏ hơn.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $T$ — số lượng truy vấn.
• Mỗi truy vấn gồm hai dòng: dòng thứ nhất là xâu nhị phân $x$, dòng thứ hai là xâu nhị phân $y$.

Dữ liệu ra

In ra $T$ số nguyên, mỗi truy vấn một dòng: giá trị $k$ làm cho ${\text{rev}}_k$ nhỏ nhất theo thứ tự từ điển.

Ràng buộc

• $1\le T\le 100$
• Mỗi xâu $x$, $y$ gồm các ký tự 0 hoặc 1, độ dài không quá ${10}^5$.
• $1\le f(y)\le f(x)$; cả hai biểu diễn đều không có chữ số $0$ ở đầu.
• Tổng độ dài của tất cả các xâu $x$ không vượt quá ${10}^5$, tổng độ dài của tất cả các xâu $y$ không vượt quá ${10}^5$.

Ví dụ