An array $A$ contains integers with the following constraints:

• $A$ contains elements in sorted order.
• Integer $i$ occurs $i \times floor(sqrt(i)) + ceil(i/2)$ times in the array. 
• All elements are greater than or equal to $1$.

You are given $Q$ queries of type:

• $L \ R$: Find the number of distinct values present in subarray $A[L...R]$. 

Note: 1-based indexing is followed.

Input format

• The first line contains an integer $Q$ denoting the number of queries.
• Next $Q$ lines contains two space-separated integers $L \ R$, denoting the query.

Output format

For each query in a new line, print the required number of distinct values.

Constraints

$1 \le Q \le 10^5 \\ 1 \le L \le R \le 10^{13}$