G - Ternary Popcount
Ceylon
2
s
1024
MB
100
点
問題文
非負整数 $N$ に対し、$f(N)$ を $3$ 進数で $N$ を表記した際の各桁の和とします。
$Q$ 個のクエリが与えられます。$i$ 番目のクエリでは $L_i \leq R_i$ を満たす非負整数 $L_i, R_i$ が与えられるので、$f(L_i), f(L_i + 1), ..., f(R_i)$ の最小値を求めて下さい。
制約
- $1 \leq Q \leq 2 \times 10^5$
- $0 \leq L_i \leq R_i \leq 10^{18}$
入力
入力は以下の形式で標準入力から与えられる。
$Q$
$L_1\ R_1$
$\vdots$
$L_Q\ R_Q$
出力
答えを $Q$ 行に出力せよ。
入力例 1
3
10 12
1000 1000
0 1000000000
出力例 1
2
4
0
- $1$ 番目のテストケースについて、 $f(10)=2$、$f(11)=3$、$f(12)=2$ より答えは $2$ です。
- $2$ 番目のテストケースについて、 $f(1000)=4$ より答えは $4$ です。
- $3$ 番目のテストケースについて、 $f(0)=0$ であり、これが最小値であるため答えは $0$ です。