Avantika

All submissions for this problem are available.

Young man named Baahubali found a mask next to a giant waterfalls. He imagined that it belonged to a beautiful girl. He was so determined to see the smile on her face that he did the unthinkable - he climbed the mighty waterfalls. When he reached the top, he met Avantika - the girl behind the mask and fell in love with her. He was shocked to learn that she was a warrior, but he was even more impressed after watching her fighting skills.

One fine day, Baahubali made a tattoo on Avantika's hand without her knowledge, and she was eventually very impressed. She asked Shiva to make more tattoos for her, and he sure doesn't want to disappoint her.

Initially, Baahubali has N bottles of paint, where each bottle is filled with paint of some color. More specifically, bottle i contains paint of color A_i, and two different bottles may contain paint of the same color. Baahubali uses 2 values L and R.

He has a secret formula which is the following: He chooses all the unique paints from bottles in the range [L, R] (both inclusive). He then arranges the paints in increasing order of their color (A_i). Assume that there are K unique paints in the range [L, R], and after arranging them in increasing order of their color value, he gets B₁, B₂, ..., B_K. He now mixes all of them by taking exactly i units of paint B_i and summing them up to get a new colored paint. More specifically, he takes sum(i * B_i) to get a new colored paint.

Avantika asked him to make M tattoos for her. Your task is to help Baahubali find the value of the new color he gets using the above method, given the L_i and R_i values for each of the M tattoos.

Input

The first line of input consists of a single integer T denoting the number of test cases. The description of T test cases follow. The first line of each test case consists of a single integer N, denoting the number of bottles of paint that Baahubali has. The second line of each test case consists of N space separated integers A₁, A_{2, ..., AN} , where A_i denotes the color of the paint in the i^th bottle. The next line of each test case consists of a single integer M, denoting the number of tattoos that Baahubali has to make. Each of the following M lines contain 2 space separated integers, where the values on the j^th line denote L_j and R_j for the j^th tattoo.

Output

For each tattoo, output the value of the color that Baahubali creates using the formula mentioned in the statement above.

Constraints

• 1 ≤ T ≤ 20
• 1 ≤ N ≤ 10⁴
• 1 ≤ M ≤ 10⁴
• 1 ≤ A_i ≤ 10⁹
• 1 ≤ L_i ≤ R_i ≤ N

Example

Input:
1
5
1 2 3 2 1
5
1 1
1 2
2 4
1 4
1 5
Output:
1
5
8
14
14

Explanation

For the first tattoo, L = 1 and R = 1, and there is only 1 unique color (= 1) in that range. Hence, the answer is 1.

For the second tattoo, there are 2 unique colors [1, 2], and the new color formed is 1*1 + 2*2 = 5.

For the third tattoo, there are 2 unique colors [2, 3], and the new color formed is 1*2 + 2*3 = 8.

For the fourth and fifth tattoos, there are 3 unique colors [1, 2, 3], and the new color formed is 1*1 + 2*2 + 3*3 = 14.