题目背景

原题链接：https://oier.team/problems/X12B。

“一旦你尝试过天空的味道，你就会永远向上仰望”——列奥纳多 达芬奇

题目描述

定义一个 01 串 $s$ 的权值为最小的 $k$ 使得 $s$ 能被分割成 $k$ 个子串，且每个子串的各个字符都相等。例如，1011110000010000 的权值为 $6$。

现有一个二进制数 $n\in[l,r]$，求 $n$ 转化为 01 字符串（不含前导零）后的权值最小是多少，即，求 $[l,r]$ 中权值最小的 $n$ 的权值。

输入格式

本题有多组测试数据，第一行输入一个整数 $T$，表示数据组数。对于每组数据：

• 仅一行，两个整数 $l,r$，以二进制形式给出。

输出格式

对于每组数据，输出一行一个整数，表示 $[l,r]$ 中权值最小的二进制数 $n$ 的权值。

2
110010000000 110110101100
1 10

3
1

提示

【样例解释】

在第一组测试数据中 $l=3200,r=3500$。可以选择 $n=3327$，其二进制表示为 110011111111，权值为 $3$。可以证明在 $[l,r]$ 的数没有更小的权值了。

在第二组测试数据中 $l=1,r=2$。可以选择 $n=1$，其二进制表示为 1，权值为 $1$。显然这是最小可能的权值。

【数据范围】

对于 $20\%$ 的数据，$l,r\le2^{20}-1$。

对于 $50\%$ 的数据，$l,r\le2^{5\times10^3}-1$。

对于另外 $30\%$ 的数据，保证二进制数 $l$ 和 $r$ 的位数相同。

对于 $100\%$ 的数据，$1\le T\le10$，$1\le l\le r\le2^{5\times10^5}-1$，且 $l,r$ 没有前导零。