It's the viva time.TA is given the responsiblity to take the viva of all students of the class.Every student of the class is associated with a number .Numbers associated with any $2$ students can be equal as well. Say there are $N$ students in the class.

TA is also bored doing the same viva stuff each time, so he does a marking gaming along with taking viva .In which he has number line , consisting of whole numbers( non - negative integers ) less than equal to 10^12. All numbers from $0$ till 10^12 .

And their will be a current position on the number line , which  is initially number $0$  .

Now he calls , one of the students among the $N$ and ask that student his/her associated value ( say $X$ ) , and now the TA has 2 options at this point , either add this value $X$ to current positon and get the new position , or other option is to , subtract this value $X$, from the current positon , to get the new positon . Now reaching the new positon , he always mark the new position .

Also he can only do the subtraction (of x) operation if the new position is valid ( .i.e non negative integer )( the new position should be on the number line)
TA can repeat the above procedure( call any student) any number of times , as he want .
Also a particular student can also be called on any number of times.

TA will mark all the possible numbers which he can mark on the number line , following the above procedure.

Note :
-> A number of number line , can be either marked or not  marked.
-> initially $0$ is marked
-> a number can be marked only once , but can be visited any number of times.

As TA has to answer something to the concerned faculty , it is necessary , that 
he atleast call Every student atleast once.
Now , TA is done with the marking strategy and has marked all the possible numbers which he can mark. 

Now suddenly professor came in from no where, and its time for the viva of the TA.
professor will provide two integers $l$ and $r$ , and now the TA needs to tell how many numbers are marked in that range.

As now TA is in trouble and ask you for help and will award you marks if you succeed.

$Input :$
First line will contain $T$, number of test cases.
Second line will have $N$, number of students in the class.
Next line will have $N$ numbers ,each denoting the value associated with each student.
Fourth line will be the $Q$ , number of query , professor asks to the TA
Next q lines , each will have 2 integer ( say $l$ and $r$) , the range in which TA need to answer the query of professor. 

$Constraints:$
1$\leq$$T$$\leq$100
1$\leq$$N$$\leq$$10^5$
1$\leq$number associated with student $\leq$$10^9$
1$\leq$$Q$$\leq$$10^5$
1$\leq$$l$,$r$$\leq$10^12 

( $15$ points )

1$\leq$$t$$\leq$10
$N$=1
1$\leq$number associated with student $\leq$$10^9$
1$\leq$$Q$$\leq$$10^5$
1$\leq$$l$,$r$$\leq$10¹²

( $85$ points)
original constraints.

$Output:$

For each test case, print $Q$ lines , answer of each query of professor in new line.