## Problem

### Read problems statements in Mandarin Chinese and Russian.

You are given an array A of integers of size N. You will be given Q queries where each query is represented by two integers L, R. You have to find the gcd(Greatest Common Divisor) of the array after excluding the part from range L to R inclusive (1 Based indexing). You are guaranteed that after excluding the part of the array remaining array is non empty.

### Input

• First line of input contains an integer T denoting number of test cases.
• For each test case, first line will contain two space separated integers N, Q.
• Next line contains N space separated integers denoting array A.
• For next Q lines, each line will contain a query denoted by two space separated integers L, R.

### Output

For each query, print a single integer representing the answer of that query.

### Constraints

• 2 ≤ T, N ≤ 100, 1 ≤ Q ≤ N, 1 ≤ A[i] ≤ 105
• 1 ≤ L, R ≤ N and L ≤ R

• 2 ≤ T, N ≤ 105, 1 ≤ Q ≤ N, 1 ≤ A[i] ≤ 105
• 1 ≤ L, R ≤ N and L ≤ R
• Sum of N over all the test cases will be less than or equal to 106.

Warning : Large IO(input output), please use faster method for IO.

### Sample 1:

Input

Output

1
3 3
2 6 9
1 1
2 2
2 3
3
1
2

### Explanation:

Test case 1: The given array is [2,6,9].

• Query 1: On excluding the range [1,1], the remaining elements are [6,9]. The gcd of 6 and 9 is 3.
• Query 2: On excluding the range [2,2], the remaining elements are [2,9]. The gcd of 2 and 9 is 1.
• Query 3: On excluding the range [2,3], the remaining elements are [2]. The gcd of 2 is 2.
Accepted
3430
Submissions
27308
Accuracy
14.2

## Code Examples

### #1 Code Example with C Programming

Code - C Programming

 #include<bits/stdc++.h>
using namespace std;
using ll = long long;

void solve()
{
int n,q;
cin>>n>>q;
int a[n+10],fw[n+10],bw[n+10];
fw[0]=bw[n+1]=0;
for(int i=1; i < =n; i++)
{
cin>>a[i];
}
for(int i=1; i < =n; i++)
{
fw[i]=__gcd(fw[i-1],a[i]);
}
for(int i=n; i>=1; i--)
{
bw[i]=__gcd(bw[i+1],a[i]);
}
while(q--)
{
int l,r;
cin>>l>>r;
cout<<__gcd(fw[l-1],bw[r+1])<<endl;
}
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);

int TC = 1;
cin >> TC;
cin.ignore();
while (TC--) solve();
} 
Copy The Code &

Input

cmd
1
3 3
2 6 9
1 1
2 2
2 3

Output

cmd
3
1
2