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² + 3¹ + 3⁰, 90 = 3⁴ + 3².

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 ≤ 10¹⁸)

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 2³²

Example

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

Output:
8
4
19
25
26