$$ f(l,r) = 2^l + 2^{l+1} + \cdots + 2^r. $$

You are given ~Q~ queries. For each query, compute the exact value of ~f(l, r)~.

Input

The first line contains an integer ~Q~ — the number of queries.

Each of the next ~Q~ lines contains two integers ~l~ and ~r~ describing one query.

Output

For each query, print the exact value of ~f(l, r)~ on a separate line.

Constraints

• ~1 \le Q \le 1000~
• ~0 \le l \le r \le 100000~

Sample Input

5
0 0
1 3
2 5
5 5
0 10

Sample Output

1
14
60
32
2047