Автор витратив всі креативні навички на попередні задачі, тому в цій умові Антона мучити не будуть. Він просто дасть вам цікаву задачку.

Вам задано масив $a$, який складається з $n$ цілих чисел. Також вам задано $q$ запитів $[l;r]$. Для кожного запиту знайдіть максимальне значення $\operatorname{sum}[tl;tr] \times \operatorname{gcd}[tl;tr]$ по всім парам ($tl;tr$), де 

\begin{itemize}
\item $l \le tl \le tr \le r$;
\item $\operatorname{sum}[tl;tr]$ --- сума усіх чисел на відрізку $[tl;tr]$;
\item $\operatorname{gcd}[tl;tr]$ --- найбільший спільний дільник усіх чисел на відрізку $[tl;tr]$.
\end{itemize}

Найбільший спільний дільник двох чисел $a$ та $b$ --- це найбільше ціле число $x$, що ділить одночасно $a$ і $b$.

Найбільший спільний дільник множини чисел --- це найбільше ціле число $x$, що ділить всі елементи множини.