Taco Subarray Sum Queries

Given an integer array, a target sum \(K\), and several queries each specifying a subarray by its starting index \(L\) and ending index \(R\) (using 1-indexed positions), your task is to count the number of continuous subarrays within the given range that sum up exactly to \(K\).

For each query, consider only the segment of the array from index \(L\) to \(R\) and determine the number of contiguous subarrays whose sum is equal to \(K\). You will be provided multiple test cases.

inputFormat

The first line contains an integer \(T\) representing the number of test cases. For each test case:

• The first line contains three integers \(N\), \(K\) and \(Q\) — the number of elements in the array, the target sum, and the number of queries respectively.
• The second line contains \(N\) integers separated by spaces, representing the array elements.
• Each of the next \(Q\) lines contains two integers \(L\) and \(R\) (\(1 \leq L \leq R \leq N\)), representing a query.

outputFormat

For each test case, output a single line containing \(Q\) integers separated by spaces. Each integer represents the count of contiguous subarrays within the segment [L, R] that sum exactly to \(K\).

3
5 5 3
1 2 3 -2 5
1 5
1 3
2 4
4 3 2
1 1 1 1
1 4
2 3
6 0 3
2 -2 3 -3 0 0
1 4
1 6
3 6

2 1 1
2 0
3 6 6