众所周知绿博有很多绿色的帽子，就像下面这样。

有一天绿博顶着许多绿帽子回家，但是路上掉了许多绿帽子。

可以将绿博回家的路程当成一个一维数轴，出发点为 1，终点为 n 。已知绿博在每个整数点 i 会掉落 ai 顶绿帽子，现在绿博很好奇，他在一段路程 [l, r] 中总共掉了多少顶绿帽子。

包含多组测试数据，第一行先输入一个正整数 T (1 <= T <= 10)，代表 T 组测试数据。

每组数据第一行输入一个正整数 n (1 <= n <= 100000)，代表终点。

第二行输入 n 个以空格隔开的非负整数 ai (1 <= ai <= 100)，表示在每个位置掉落的绿帽子的数量。

第三行输入一个非负整数 q (0 <= q <= 100000)，表示绿博有 q 次询问。

接下来有 q 行，每次输入以空格隔开的两个正整数 l 、 r (1 <= l <= r <= n)，代表绿博询问区间 [l, r] 中总共掉落了多少个绿帽子。

对于每组数据，输出 q 行，每行输出一个非负整数，代表绿博在所询问的区间掉落的绿帽总数。

1
5
1 2 3 4 5
3
1 2
3 3
4 5

3
3
9