Pirotexnik - 2#4506
Məzuniyyətdən sonra, daha əvvəl haqqında danışdığımız Vitaliy böyük populyarlıq qazandı və ölkə üzrə müxtəlif yerlərdə atəşfəşanlıq təşkil etmək üçün dəvətlər almağa başladı. Düzdür, Vitaliy hələ də eyni iki maddədən, və , istifadə edir, amma bu maddələrin miqdarı xeyli artıb. Sənin vəzifən ona kömək etməyə davam etmək və hər bir sorğu üçün partlayışın gücünü hesablamaqdı.
Atəşfəşanlığın həm gözəl, həm də güclü olması üçün, partlayışın gücü maksimum olmalıdır. Partlayışın gücü aşağıdakı düsturla hesablanır:
burada a, a+1, \ldots, b-1, b üçün,
və isə birinci və ikinci maddələrin miqdarıdır.
Birinci sətirdə tək tam ədəd 1 \le t \le 900\,000 — sorğuların sayı verilir. Sonrakı sətirdə isə sorğuların özləri verilib: a_i və b_i — iki maddənin miqdarı (0 \le a_i \le b_i \le 10^{17}).
Hər bir sorğu üçün partlayışın gücünü ayrı sətirdə çap et.
Nümunə 1