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.

题目描述

2333城是一个巨大的城市，之所以叫这个名字，是因为城市中遍布着数不尽的三岔路口和一个二岔路口。

具体来说，城中有无穷多个路口，每个路口有唯一的一个正整数标号。除了1号路口外，每个路口都连出正好3条道路通向另外3个路口：编号为 $x(x>1)$ 的路口连出3条道路通向编号为 $2x$，$2x+1$ 和 $\lfloor \frac{x}{2} \rfloor$ 的3个路口。1号路口只连出两条道路，分别连向2号和3号路口。

所有道路都是可以双向通行的，并且长度都为1。现在，有n个问题：从路口 $x$ 到路口 $y$ 的最短路长度是多少？

输入格式

第一行包含一个整数 $T$，表示询问数量；

接下来 $T$ 行，每行包含两个正整数 $x,y$，表示询问从路口 $x$ 到路口 $y$ 的最短路长度。

输出格式

输出 $T$ 行，每行包含一个整数，表示对每次询问的回答。如果对于某个询问不存在从 $x$ 到 $y$ 的路径，则输出 -1。

1
2 3

2

1
4 7

4

2
8 9
201 1010

2
14

提示

对 $30\%$的数据，$x,y\le 20$；

对 $60\%$ 的数据，$x,y\le 10^5，T\le 10$；

对 $100\%$ 的数据，$x,y\le 10^9，T\le 10^4$。