Hello, 2048!

Time limit1sMemory limit512 MB

Summary

Given l and r, find how many times the number formed by concatenating 2^l through 2^r in decimal divides evenly by 2, without building the huge number.

Level: Hard8 of 10
Topics: Math, Number theory, Implementation
Solved: No attempts yet

Problem

Sungbin, who studies computer science, is especially fond of powers of two. One day, while looking at a calendar, he realized that the year 2048 was approaching. He wondered how likely it was for an arbitrary person to live through a year that is a power of two, and thought that this probability would decrease as time passed.

While staring at the number 2048, Sungbin noticed something interesting: it contains the digits 2, 4, and 8, which are themselves powers of two. This led him to the following question.

Let $N$ be the decimal number formed by writing $2^l, 2^{l+1}, \cdots, 2^r$ in decimal notation and concatenating them in that order. How many times can $N$ be divided by 2 consecutively?

The number can become far too large to build directly. Write a program that answers Sungbin's question.

Input

The first line contains an integer $T$ , the number of test cases.

Each test case consists of two integers $l$ and $r$ separated by a space.

Output

For each test case, print one line containing the answer to Sungbin's question.

Constraints

$1 \leq T \leq 10^5$
$0 \le l \le r \le 10^9$

Examples1

Example 1
Input
```
3
0 3
2 5
1 2
```
Expected output
```
5
5
3
```