某一天，calfcamel 问二哥，有道数学题怎么做呀？二哥看了一下说我不会呀，于是二哥找到了你，请你帮他解决这个问题，这样二哥就可以鄙视 calfcamel 数学菜了。
给你一个长度为 $n$ 的数组 $a[i]$，有 $q$ 个询问，对于每次询问 $[l,r]$，输出
$$\sum_{i=l}^r a_i(i-l+1)$$
也就是输出 $[l,r]$ 这段区间上，第一个数乘以一，第二个数乘以2，第三个数乘以3……的和。
第一行为一个 $T\ (1\le T\le 5)$，表示有 $T$ 组数据。对于每组数据：
第一行是一个 $n\ (1\le n \le 100\ 000)$
第二行有 $n$ 个数 $a_1,a_2,\cdots,a_n \ (0\le a_i \le 100000)$
第三行有一个 $q\ (1\le q \le 100\ 000)$，表示询问的数目
接下来 $q$ 行，每行有两个整数 $l,r$
对于每一组数据，第一行输出Case x: 和一个空格（由于网站原因样例中不显示这个空格）
接下来 $q$ 行，每行输出询问的答案
文件最后使用换行符结束文件
2 3 1 2 3 1 1 3 5 1 2 3 4 5 3 1 5 2 4 3 5\n \n · · \n \n · \n \n · · · · \n \n · \n · \n · \n
Case 1: 14 Case 2: 55 20 26· \n \n · \n \n \n \n
数据比较大，C / C++请使用 scanf 读入 ，使用 cin 可能会超时。
本题目最后答案超出 int，C / C++请使用 long long 防止溢出。