TREENUM2 - The art of tree numbers

no tags 

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

hide comments
kartikeya : 2015-06-28 22:03:38

O(T*log(l)+log(r)) giving tle !!!

Last edit: 2015-06-29 07:25:20
i_love_inu143: 2015-06-12 15:50:51

@mandrathax :
can you provide O(T) complexity ?

Kata: 2015-06-12 10:30:46

@ujzwt4it :
Please read your code carefully and you will find it easily. If you can't find it, I think you should solve some basic problems before this problem.

ujzwt4it: 2015-06-11 17:05:38

it doesn't work with the big input, what could be the problem?

Kata: 2015-06-11 16:36:15

@ujzwt4it :
Did you try run your code with big input, i.e L = 1, R = 10^18 ?

ujzwt4it: 2015-06-11 15:11:09

I m getting NZEC though the code runs perfectly fine on ideone

Kata: 2015-06-05 15:41:40

Ameya Panse :
I tried submit your code and it only got TLE while running test 0. Your algo can't pass the time limit. Try more !

Ameya Panse: 2015-06-04 16:09:16

I'm getting TLE while the code is compiling. Is that how its supposed to work?

Kata: 2015-06-03 07:44:13

@mandrathax :
Thanks. I have no idea about O(T) solution now, but let's think about it ! So interesting !

mandrathax: 2015-06-03 01:11:28

This problem is AWESOME! Took me 4 TLEs and 2 WAs and went through 3 algos before getting AC.
Seems like you can make it in O(T) after all


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