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 ☹

Limits: 1s, 512 MB

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 A1, A2, … , An denoting the elements of the array.

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

Constraints :

  • 1 ≤ T ≤ 100
  • 1 ≤ N ≤ 105
  • 1 ≤ Ai ≤ 1012
  • 1 ≤ K ≤ 1018
  • 1 ≤ A ≤ B ≤ 1018

Note: sumation of N in in all test cases doesn’t exceed 106

Output

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

Samples

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

Author
Discussion
Submit

Login to submit