You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

注意：这 不 是 lca&*!@#()!#模?>.\版*题!@$=@。

题目描述

给定一棵根为 $1$ 的无穷个节点的二叉树，其中节点 $i$ 的两个儿子为 $2i$ 和 $2i+1$。

多次询问，每次给定两个正整数 $x,y$ 的二进制表示，求这两个点在树上的距离。

输入格式

本题单个测试点内有多组数据。

第一行一个整数 $T$，表示数据组数。

接下来 $T$ 行，每行两个整数 $x,y$ 描述一组数据，注意 $x,y$ 是二进制形式表示。

输出格式

共 $T$ 行，每行一个整数表示答案。

样例

4
1 10
100 111
11111 11110
10101 10110

1
4
2
4

样例解释

对于第一组数据，树上节点 $2$ 是节点 $1$ 的儿子，所以节点 $1,2$ 距离为 $1$。

对于第二组数据，树上节点 $4,7$ 距离为 $4$。

数据规模与约定

本题只有 $4$ 个点。

记 $x,y$ 在二进制表示下长度最大为 $s$。

• $\text{\#1}$（13 pts）：$s \leq 5$。
• $\text{\#2}$（20 pts）：$s \leq 20$。
• $\text{\#3}$（20 pts）：$s \leq 60$。
• $\text{\#4}$（47 pts）：$s\leq 10^4$。

对于所有数据，$1 \leq T \leq 100$，且 $x,y$ 没有前导 $0$。