You are given two positive integers $L$ and $R$. Find the number of integers in the range $[L,\ R]$ that can be represented as the difference of two squares. In other words, find the number of integers $X$ in the range $[L,\ R]$ such that $X = P^2 - Q^2$ where $P$ and $R$ are integers.

Input format

• The first line contains $T$ denoting the number of test cases.
• Each of the next $T$ lines contain two integers $L$ and $R$..

Output format

For each test case, you are required to print exactly $T$ lines each containing only 1 positive integer.

Constraints

$1 \leq T \leq 10^5\\ 1 \leq L,\ R \leq 10^9$