You have been given a Unimodal function:
f(x) = 2x^2 - 12x + 7
with N intervals. For each interval, you will be given two integer values l and r, where and you need to find the minimum value of f(x) where x will be in the range [l, r] (both inclusive).Input Format
The first line will consist of one integer N denoting the number of intervals. In the next N lines, each line contains 2 space-separated integers, l, and r denoting the range of interval.
Output Format
Print N lines, where ith line denotes the minimum value of f(x), where x will be in the range [li, ri];
Constraints
1 <= N <= 10^5 -10^6 <= l <= r <= 10^6
Example
Input
1 6 8
Output
7