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
Sushovan Sen: 2021-11-12 12:53:45

Can anyone provide answer for
1
5487542154875487 98875465876548974

Is it 2238851352?

re -> Yes it is.

Last edit: 2021-11-12 13:13:25
smso: 2020-02-05 08:53:21

precompute powers of 3 to beat TLE

nadstratosfer: 2019-12-28 03:33:52

Enjoyed breaking it down. Glad I haven't solved all problems from this genre yet ;)

i_own_you: 2016-07-15 22:48:52

@hm_98 nope, its 416707434. Nice question, accepted in O(T*logR) :)

hm_98: 2016-07-03 13:50:08

Is output for L = 1 and R = 10^18 is 4184870227?
Getting WA :(

:.Mohib.:: 2015-11-12 10:58:04

Finally did it....Thanks for really beautiful problem.....!!

elise: 2015-09-05 02:55:14

Unsigned long long int can help a lot.
Complexity of the solution I got AC with is O(T)*O(logR), beware of the time used to calculate exp(x, y).
Nice problem.

Last edit: 2015-09-05 02:57:26
saurabh: 2015-07-31 22:39:48

Will java code not accept at all? I tried optimizing highly but to no avail. Am I wasting my time?
Please reply @Kata (My solution ID 14793154)

Last edit: 2015-07-31 22:40:27
Shivaraj Lakka: 2015-07-31 08:50:39

I implemented it in O(T).. but constantly getting WA.!!!
its passing all the given sample inputs.. :-(
@Author, can you look into 14788142 submission..
or provide o/p for L=1 and R=10^18..

Last edit: 2015-07-31 08:51:58
goyal: 2015-07-21 17:01:18

nice que:)


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