\begin{problem}{Поломка Бамблби}{bumblebee.in}{bumblebee.out}{2 секунды}{256 мегабайт}

%Автор задачи: Дмитрий Филиппов
%Автор условия: Дмитрий Филиппов

После очередного боя с десептиконами у Бамблби что-то сломалось. Теперь он делает непонятные вещи. 
Например, сейчас он пытается решить некоторую странную задачу. Опишем ее условие.

Введем две функции, определеные на множествах положительных натуральных чисел.
Первой функцией будет $mex(a_1, a_2, \dots, a_n)$~--- наименьшее положительное 
натуральное число, которого нет среди чисел $a_1$, $a_2$, \dots, $a_n$. Второй функцией 
будет $gcd(a_1, a_2, \dots, a_n)$~--- наибольший общий делитель чисел $a_1$, $a_2$, \dots, $a_n$
Бамблби сгенерировал массив натуральных чисел, а теперь хочет уметь делать следующую операцию:
для произвольных чисел $l$ и $r$ перебирать все подмножества отрезка массива от $a_l$ до $a_r$ включительно,
для каждого непустого подмножества считать его $mex$, а потом считать $gcd$ всех получившихся $mex$-ов (несложно понять, 
что их может оказаться $2^{r - l + 1} - 1$).

К сожалению, вычислительная мощность Бамблби не позволяет ему решать эту задачу быстро. Помогите ему.

\InputFile                            
В первой строке входного файла дано число $n$ ($1 \le n \le 10^5$)~--- длина массива, сгенерированного Бамблби.

Во второй строке дано $n$ разделенных пробелами чисел $a_i$ ($1 \le a_i \le 10^9$)~--- числа в массиве, сгенерированном Бамблби.

В третьей строке входного файла дано число $q$~--- количество запросов ($1 \le q \le 10^4$).

В каждой из следующих $q$ строк входного файла записаны два числа $l$, $r$ ($1 \le l \le r \le n$) ~--- 
отрезок, на котором надо посчитать значение функции.
             
\OutputFile
В выходной файл выведите $q$ строк~--- в $i$-ой строке выведите ответ на $i$-ый запрос.

\Examples
\begin{example}%
\exmp{
4
1 2 3 4
2
1 1
1 4
}{
2
1
}%
\end{example}

\Testing
Первая группа тестов состоит из тестов, для которых выполняется ограничение $n \le 4$. Баллы 
за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет $20$ баллов.

Вторая группа тестов состоит из тестов, для которых выполняется ограничение $n \le 1000$. Баллы 
за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет $40$ баллов.

Третья группа тестов состоит из тестов, для которых выполняется ограничение $n \le 10^5$. Баллы 
за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет $40$ баллов.

Обратите внимание на возможность узнать результат проверки вашего решения на всех группах тестов, кроме последней, 
нажав на ссылку <<\texttt{Request feedback}>> на вкладке <<\texttt{Runs}>>.

\end{problem}
