Поломка Бамблби

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

Введем две функции, определеные на множествах положительных натуральных чисел. Первой функцией будет $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$).

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

В первой строке входного файла дано число $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$) --- отрезок, на котором надо посчитать значение функции.

В выходной файл выведите $q$ строк --- в $i$-ой строке выведите ответ на $i$-ый запрос.