Піротехнік - 2#4506
Після закінчення університету Віталій, про якого вже згадували раніше, здобув значну популярність і почав отримувати запрошення організовувати феєрверки по всій країні. Справедливо сказати, що його навички не покращились; він як і раніше використовує ті ж дві речовини і , але їх кількість істотно зросла. Ваше завдання — і надалі допомагати йому, надаючи потужність вибуху для кожного його запиту.
Щоб феєрверки були красивими та потужними, потрібно максимізувати потужність вибуху. Потужність вибуху обчислюється за такою формулою:
для a, a+1, \ldots, b-1, b,
де і — це кількості першої та другої речовини відповідно.
Перший рядок містить одне ціле число 1 \le t \le 900\,000 — кількість запитів. У наступних рядках наведені самі запити: числа a_i і b_i, які є кількостями двох речовин (0 \le a_i \le b_i \le 10^{17}).
Для кожного запиту виведіть потужність вибуху у окремому рядку.
Приклад 1