#P0006. 黑板游戏
黑板游戏
题目描述
Waylon 在黑板上写下了从 到 (含边界)的所有整数。
在一次运算中,他可以选择完成以下操作:
- 在黑板上选出两个数字 和 擦去,然后在它们的位置上写下数字 和 。(这里的 表示向下取整)。
要使黑板上的所有数字都等于 ,Waylon 最少需要进行多少次运算?我们可以证明这总是可能的。
输入格式
第一行包含一个整数 ( ) - 测试用例的数量。
每个测试用例的唯一一行包含两个整数 和 ( )。
输出格式
对于每个测试用例,输出一个整数,即使黑板上的所有数字等于 所需的最少运算次数。
样例 #1
样例输入 #1
4
1 3
2 4
199999 200000
19 84
样例输出 #1
5
6
36
263
提示
在第一个测试用例中,我们可以执行 操作如下:
$$1,2,3 \xrightarrow[x=1,\,y=2]{} 3,0,3 \xrightarrow[x=0,\,y=3]{} 1,0,3 \xrightarrow[x=0,\,y=3]{} 1,0,1 \xrightarrow[x=0,\,y=1]{} 0,0,1 \xrightarrow[x=0,\,y=1]{} 0,0,0 .$$