Good number is a number D, such that frequency of odd integers in the range 1  to D divides it. If any number defies this property, then it can be classified as Bad number.

You are given an array A and Q  tasks of the form L R, you have to find what is the minimum number of steps needed to make subarray from L to R balanced.

Any subarray is said to be balanced if count of Good number(s) is not less than count of Bad number(s) in that subarray. In every step, you can either increase the value of some array element by 1 or you can decrease an array element by 1.

Input Format:
First line contains an integer T, denoting the number of testcases.

In each test case:
Firstl line contains N, the number of elements in array A.
Next line contains N space separated integers denoting array elements.
Next line contains , the Q number of queries.
Each of the next lines contains two space separated integers L and R.

Output Fomat:
For each task, print total number of steps needed to change the subarray such that subarray from L to R

is balanced.
Answer for each task should be printed in a new line.

Constraints:

1<= T <= 2

1<= N,Q <= 50000

1<= A_i <= 10⁹

1<= L <= R <= N