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: A₁, A₂, .., A_N. You are allowed to do a single type of operation: increase or decrease an arbitrary element A_i 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: A_{L + 1} - A_L = A_{L + 2} - A_{L + 1} = ... = A_R - A_{R - 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 A₁, A₂, .., A_N. 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 ≤ A_i ≤ 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.