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