После выпускного вечера Виталий, о котором мы упоминали в предыдущей задаче, приобрёл большую популярность и его стали приглашать для организации феерверков по всей стране. Справедливым будет отметить, что Виталий не совершенствовал свои навыки и использует все те же два вещества a и b, однако значительно возросли их количества. Вам нужно и далее помогать нашему герою и для каждого его запроса предоставлять информацию о силе взрыва.
Напомним, что для того, чтобы феерверк был красивым и мощным, нужно, чтобы сила взрыва була максимальной. Сила взрыва расчитывается по формуле:
a a+1 ... b-1 b,
где a иа b - количества первого и второго вещества соответственно.
В первой строке задано единственное число 1 ≤ t ≤ 900000 - количество запросов. В последующих t строках заданы сами запросы: числа a_i и b_i - количества двух веществ (0 ≤ a_i ≤ b_i ≤ 10^17).
Для каждого запроса в единственной строке выведите силу взрыва.