Description

已知数列a[N]，给定某个区间[L，R]（L≠R），找出一个尽可能大的整数G，使得任意abs(ai-aj)>=G（ L<= i ,j<= R,i!=j ）。abs(x)表示x的绝对值。

Input

先输入组数T，表示有T组数据。
每组数据第一行输入数列长度N和询问次数Q。
第二行输入N个数字表示数列a。
之后输入Q个询问
每个询问输入两个数字L,R，表示区间的左右界，包括L和R。
T<=5，2<=n<=100000，1<=q<=10000，0<=ai<=1000，0<= L < R 。

Output

每组数据第一行输出“Case X:”，X为组数，从1开始。
从第二行开始输出每个询问的结果。

Sample Input

2
5 3
10 2 3 12 7
0 2
0 4
2 4
2 1
1 2
0 1

Sample Output

Case 1:
1
1
4
Case 2:
1

HINT

Source

NBU xuenene