Remote Training on Programming

Consider a sequence of N interegs x_i. In order to run a number-theoretic statistical experiment, a random set of queries to this sequence is generated.

Each query is a pair of integers <r, q>. The result of a query will be the Greatest Common Divisor of the members (GCD) in the subsequence starting with x_r and ending with x_q.

For example, if sequence (1, 2, 4, 6, 12) is given then for query <1, 5> the result equals to GCD(1, 2, 4, 6, 12) = 1, for query <2, 4> the result will be GCD(2, 4, 6) = 2, and for query <4, 5> the result will be GCD(6, 12) = 6.

Your task is to write a program, which will construct a set of results, given a number sequence (x_i) and a set of queries.

Note that the queries may be repeated.

Input

The first line of the input file contains two integers (N, M) separated by one or several spaces. Number N is the number of elements in the sequence of numbers. (1<N<=10000). Number M is the number of queries (0<M<=100000).

The second line contains N integers x_i that form the sequence. The numbers are delimited by one or more spaces (0<x_i<=10⁹).

Then M lines follow, containing number pairs (r_i, q_i) each. The numbers in a pair are delimited by one or more spaces. A pair is a query for GCD computation of the members x_ri ... x_qi (0<r_i,q_i<=N, r_i<q_i).

Output

The first line of the output file must contain the number M. The following M lines must contain the answers. The i-th line of those M lines must contain the answer to the query <r_i, q_i>.

Samples