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\)