The sum of gcd
Description:
You have an array A,the length of A is n
Let f(l,r)=∑ri=l∑rj=igcd(ai,ai+1....aj)
Input:
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
First line has one integers n
Second line has n integers Ai
Third line has one integers Q,the number of questions
Next there are Q lines,each line has two integers l,r
1≤T≤3
1≤n,Q≤104
1≤ai≤109
1≤l<r≤n
First line has one integers n
Second line has n integers Ai
Third line has one integers Q,the number of questions
Next there are Q lines,each line has two integers l,r
1≤T≤3
1≤n,Q≤104
1≤ai≤109
1≤l<r≤n
Output:
For each question,you need to print f(l,r)
Sample Input:
2 5 1 2 3 4 5 3 1 3 2 3 1 4 4 4 2 6 9 3 1 3 2 4 2 3
Sample Output:
9 6 16 18 23 10
Source:
Submit