SP24032 TREENUM2 - The art of tree numbers

A number is called a tree\_num while it can be partition into sum of some distinct powers of 3 with natural exponent. Example : 13 and 90 are tree\_num because 13 = 3 $ ^{2} $ + 3 $ ^{1} $ + 3 $ ^{0} $ , 90 = 3 $ ^{4} $ + 3 $ ^{2} $ . Let $ tree\_num(i) $ be the i-th largest tree\_num. Example : $ tree\_num(1) = 1 $ , $ tree\_num(2) = 3 $ , $ tree\_num(5) = 10 $ , … Let $$ F(L, R) = \sum _{i = L}^R tree\_num(i) $$ Your task is to find F(L, R) with some given L, R.

\- First line : an integer T – number of testcases (1 \- Next T lines : each line contains two number – L and R (1

\- For each pair (L, R), output a line containing the value F(L, R). Since those values can be very large, just output them modulo 2 $ ^{32} $