#P0006. 黑板游戏

黑板游戏

题目描述

Waylon 在黑板上写下了从 ll 到 rr (含边界)的所有整数。

在一次运算中,他可以选择完成以下操作:

  • 在黑板上选出两个数字 xx 和 yy 擦去,然后在它们的位置上写下数字 3x3x 和 ⌊y3⌋\lfloor \frac{y}{3} \rfloor 。(这里的 ⌊∙⌋\lfloor \bullet \rfloor 表示向下取整)。

要使黑板上的所有数字都等于 00 ,Waylon 最少需要进行多少次运算?我们可以证明这总是可能的。

输入格式

第一行包含一个整数 tt ( 1≤t≤1041 \leq t \leq 10^4 ) - 测试用例的数量。

每个测试用例的唯一一行包含两个整数 ll 和 rr ( 1≤l<r≤2⋅1051 \leq l < r \leq 2 \cdot 10^5 )。

输出格式

对于每个测试用例,输出一个整数,即使黑板上的所有数字等于 00 所需的最少运算次数。

样例 #1

样例输入 #1

4
1 3
2 4
199999 200000
19 84

样例输出 #1

5
6
36
263

提示

在第一个测试用例中,我们可以执行 55 操作如下:

$$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 .$$