Number Game#13074

Number Game

1 second
256 megabytes

Marta is playing a game with a number written on a board in binary without leading zeros. Initially, a positive number is written on the board.

In one move, Marta performs two actions in the following order:

  1. She erases any number of zeros (possibly none) from the representation and appends any number of zeros (possibly none) at any positions in the representation, so that it does not start with a zero. It is not allowed to erase or append ones.

  2. She increases the written number by and writes the result in its place, again in binary without leading zeros.

Marta wins if, after one of her moves, the positive number is written on the board. If n = m, she wins immediately, without making a single move. Find the minimum number of moves in which Marta can win, or report that it is impossible to win.

Input

The first line contains a single integer (1 \le t \le 1000) — the number of test cases.

Each of the next lines contains two positive numbers and (1 \le n, m), written in binary without leading zeros and separated by a space.

It is guaranteed that 1 \le |n|, |m| \le 1000, where is the number of digits in the binary representation of .

Output

For each test case, output on a separate line a single integer — the minimum number of moves, or if it is impossible to win.

Examples

Example 1

Loading
Loading

Note

In the first test case, n = 6 = \texttt{110}, m = 14 = \texttt{1110}. Marta can win in two moves:

  • Move 1: Marta appends a zero at the end, \texttt{110} \to \texttt{1100} = 12, and increases the number: 13 = \texttt{1101}.

  • Move 2: Marta erases and appends nothing, and increases the number: 14 = \texttt{1110}.

In the third test case, it is impossible to obtain m = 1.

In the fourth test case, n = m, so Marta wins immediately.