После выпускного вечера Виталий, о котором мы упоминали в предыдущей задаче, приобрёл большую популярность и его стали приглашать для организации феерверков по всей стране. Справедливым будет отметить, что Виталий не совершенствовал свои навыки и использует все те же два вещества \textbf{a} и \textbf{b}, однако значительно возросли их количества. Вам нужно и далее помогать нашему герою и для каждого его запроса предоставлять информацию о силе взрыва. Напомним, что для того, чтобы феерверк был красивым и мощным, нужно, чтобы сила взрыва була максимальной. Сила взрыва расчитывается по формуле: \includegraphics{https://static.e-olymp.com/content/7e/7e838c0f60f64deef9d13ec9a874ce43b20530ea.jpg} \includegraphics{https://static.e-olymp.com/content/7e/7e838c0f60f64deef9d13ec9a874ce43b20530ea.jpg} \includegraphics{https://static.e-olymp.com/content/7e/7e838c0f60f64deef9d13ec9a874ce43b20530ea.jpg} \includegraphics{https://static.e-olymp.com/content/7e/7e838c0f60f64deef9d13ec9a874ce43b20530ea.jpg} \textbf{a} \textbf{a+1} ... \textbf{b-}1 \textbf{ b}, где \textbf{a} иа \textbf{b} - количества первого и второго вещества соответственно. \InputFile В первой строке задано единственное число \textbf{1} ≤ \textbf{t} ≤ \textbf{900000} - количество запросов. В последующих \textbf{t} строках заданы сами запросы: числа \textbf{a_i} и \textbf{b_i} - количества двух веществ (\textbf{0} ≤ \textbf{a_i} ≤ \textbf{b_i} ≤ \textbf{10^17}). \OutputFile Для каждого запроса в единственной строке выведите силу взрыва.