# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

## This is Too Hard ☹

Many many years ago there was a small country . And all the people there were very weird. They liked unusual stuffs and had unusual habits. But those people were very good at technical stuffs. Anyways that is not the important thing here. In that city was a genius boy named **Ezio**. He was so good at math stuff that people started to get jealous of him. And day by day he also got cocky. His math teacher was **Tahmid** sir. Who is very cunning and wise. And he made a problem for him to break **Ezio’s** cockyness.
So he gave **Ezio** this problem which he was unable to solve.

Now, you are given the same problem. You are a very good programmer can you solve the task with your awesome coding skills.

You are given an array of **N** integers. You need to count the number of contiguous sub-segment , which has a sum divisible by **K** and the sum is between **A** and **B**.

### Input

There will T test cases.

Eveny case will have 3 lines each. First line contain N the number of integers in the array. The second line will contain **N** integers **A _{1}, A_{2}, … , A_{n}** denoting the elements of the array.

Third line will contain three integers **K**, **A** and **B**.

**Constraints :**

- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 10
^{5} - 1 ≤ A
_{i}≤ 10^{12} - 1 ≤ K ≤ 10
^{18} - 1 ≤ A ≤ B ≤ 10
^{18}

Note: sumation of N in in all test cases doesn’t exceed 10^{6}

### Output

Print exactly T lines, each containing a single integer which is the answer to the corresponding test case.

### Samples

Input | Output |
---|---|

1 5 1 2 3 4 5 3 1 15 | Case 1: 7 |

#### IamHot

→