Pyrotechnician - 2#4506
After graduation, Vitaliy, whom we mentioned earlier, gained significant popularity and began receiving invitations to organize fireworks displays across the country. It is fair to say that Vitaliy's skills have not improved; he still uses the same two substances, and , but their quantities have increased considerably. Your task is to continue assisting him by providing the explosion's power for each of his requests.
To make the fireworks both beautiful and powerful, the explosion's power must be maximized. The power of the explosion is calculated using the following formula:
for a, a+1, \ldots, b-1, b,
where and are the quantities of the first and second substances, respectively.
The first line contains a single integer 1 \le t \le 900\,000 — the number of requests. The following lines contain the requests themselves: numbers a_i and b_i, which are the quantities of the two substances (0 \le a_i \le b_i \le 10^{17}).
For each request, output the explosion's power on a separate line.
Example 1