D-小苯的数字集合_牛客周赛 Round 86

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小苯有一个可重的数字集合 $\Bbb N$ ，初始时，集合中恰好有两个正整数 $x$ 和 $y$ 。
$\hspace{15pt}$ 现在，小苯可以执行若干轮操作，每一轮操作他都会从 $\Bbb N$ 中选择一个数字 $a$ 和另一个数字 $b$ ，并从下述四种中选择一种进行：
$\hspace{23pt}\bullet$ 将 $a$ 与 $b$ 进行位与运算（ $\operatorname{and}$ ）的结果加入集合。
$\hspace{23pt}\bullet$ 将 $a$ 与 $b$ 进行位或运算（ $\operatorname{or}$ ）的结果加入集合。
$\hspace{23pt}\bullet$ 将 $a$ 与 $b$ 进行位异或运算（ $\operatorname{xor}$ ）的结果加入集合。
$\hspace{23pt}\bullet$ 将 $a$ 与 $b$ 的最大公约数（ $\gcd$ ）加入集合。
$\hspace{15pt}$ 小苯想知道，最少需要经过多少轮操作，才能使得自己的数字集合中出现数字 $0$ ，请你帮他算一算吧。

$\hspace{15pt}$ 如果您需要更多位运算相关的知识，可以参考 OI-Wiki的相关章节。
$\hspace{15pt}$ 最大公约数，指两个整数共有约数中最大的一个。例如， $12$ 和 $30$ 的公约数有 $1,2,3,6$ ，其中最大的约数是 $6$ ，因此 $\gcd(12,30)=6$ 。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
在一行上输入两个正整数  代表集合中的初始数字。

输出描述:

对于每一组测试数据，新起一行。输出一个整数，代表最少需要经过的轮数。

示例1

输入

复制

2
1 1
2 3

输出

复制

1
2

说明

对于第一组测试数据，选择 ，进行一次位异或运算，得到 。

对于第二组测试数据：
第一轮，选择 ，进行一次位与运算，得到 ；
第二轮，选择 ，进行一次位异或运算，得到 。
我们可以证明，最少需要进行  轮操作。