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 = 32 + 31 + 30, 90 = 34 + 32.

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.

Input

- First line : an integer T – number of testcases (1 ≤ T ≤ 100000)

- Next T lines : each line contains two number – L and R (1 ≤ L ≤ R ≤ 1018)

Output

- 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 232

Example

Input:
5
1 3
3 3
4 5
6 7
2 5

Output:
8
4
19
25
26

Added by:Kata
Date:2015-05-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:TREENUM

hide comments
2015-05-31 21:33:54
hmmmm.. this problem is real difficult
2015-05-30 02:05:52 Kata
@utkarsha gaumat :
Yes. Please read the problem text carefully.
2015-05-29 21:11:02 utkarsha gaumat
is the 6 7 test case answer correct??
2015-05-29 14:47:20 Kata
@eightnoteight Thanks.
@mehmetinal Nice suggestion. But the name "tree_num" was the name chose by the original problems's author, so I think It's better to keep it :D
2015-05-29 13:34:21 eightnoteight
@Kata
can you please help me,
i'm getting TLE(14348714), i couldn't figure out where it is consuming time and also couldn't optimise it more!
my complexity is O(nlogn)

UPD: never mind, I just got it. I'm doing a lot of useless computations.
nice problem by the way. :)

Last edit: 2015-05-29 14:20:44
2015-05-28 19:08:01 mehmetin
Good problem. It would be better if "tree_num" in the description is changed as "three_num", that would make more sense.
2015-05-28 00:21:46
@tjandra I am using Javascript. That makes it more interesting! :)
2015-05-28 00:01:03 (Tjandra Satria Gunawan)(曾毅昆)
@harshabn808: Time limit is OK, my unoptimized code easily got AC . Although it's hard or even impossible for slow languages like python or java.
2015-05-27 20:44:37
Are you sure about the time limit?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.