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$ ($1 ≤ T ≤ 100$) test cases.

Every case will have 3 lines each. First line contain $N$ the number of integers in the array. The second line will contain $N$ ($1 ≤ N ≤ 10^5$) integers $A_1$, $A_2$, ..., $A_n$ ($1 ≤ A_i ≤ 10^{12}$) denoting the elements of the array.

Third line will contain three integers $K$ ($1 \le K \le 10^{18}$), $A$ and $B$ ($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.

Sample

Input	Output
1 5 1 2 3 4 5 3 1 15	Case 1: 7