algorithmic-substring

In Mathematics arithmetic sequence is a sequence of numbers such that the difference between any two consecutive numbers is constant. 

You are given a sequence A that consists of N  integers: A1, A2, .., AN. You are allowed to do a single type of operation: increase or decrease an arbitrary element Ai exactly by 1. 

Your task is calculate the minimum number of operations needed to change a substring A [L, R] into an arithmetic sequence in which two consecutive elements differ exactly by K. That means, after applying  operations needed following condition should be satisfied:  AL + 1 - AL = AL + 2 - AL + 1 = ... = AR - AR - 1 = K. 

Input

The first line is T - the number of test cases. Then T test cases follow. 

Each test consists of several lines. The first line consists of two integers N and K — the number of elements in the sequence A and the desired difference between two consecutive elements in arithmetic sequence. The second line contains N integer numbers A1, A2, .., AN. The next line contains a single   integer Q —  the number of queries you have to answer. Then Q lines follow, each containing two integers L and R.

Output

For every query print the minimum number of operations needed to change substring A [L, R] into an arithmetic sequence where any two consecutive elements differ exactly K.

Constraints
1 ≤ T ≤ 10
1  ≤ N ≤ 100000
0  ≤ K  ≤ 10^8
-10^8  ≤ Ai ≤ 10^8
1  ≤ Q  ≤ 100000
1  ≤ L  ≤ R  ≤ N
10% number of tests in which N,  Q , K ≤ 10.
30% number of tests in which 1 ≤ N,  Q ≤ 3000.
10% number of tests in which K = 0.
30% number of tests in which L = 1.

SAMPLE INPUT
2
3 1
1 1 3
2
1 1
1 3
5 2
1 2 3 4 5
3
4 5
1 3
1 5

SAMPLE OUTPUT
0
1
1
2
6

Source: hackerearth | Difficulty: HARD


Solutions: