Sofdor Ali's Restaurant
One of Sofdor Ali’s greatest accomplishment was his Biriyani restaurant! Unlike the traditional restaurants, his chefs were all, you know, rats! He had broken the delicate art of cooking Biriyani into different small tasks and trained the rats for each of the tasks. His strategy was perfect and his Biriyani was the best. But the rats never stopped producing Biriyani. Even during the night time, when none of the customers came for a feast. Eventually, Sofdor Ali had to close his project and had to focus on his next endeavor.
We all know that. But what happened to those rats? Had they given up something for which they really worked so hard? No. They have decided to open Biriyani restaurants on their own. They have chosen the longest road of Dhaka city and opened Biriyani shops at the roadside. Since all the rats from Sofdor’s restaurant were close friends, they decided to open shops close to each other. So they have chosen one side of the road, and opened N shops side by side, one for every rat.
Now, you and your friends have decided to go and taste those delicious Biriyani. But there’s a catch, every restaurant makes a fixed amount of Biriyani every day. And if you buy from one restaurant, you have to buy all of their products. it’s weird, but after all, they are rats and you need to go by their rule. This weird restriction creates one more problem, after buying Biriyani from one or more restaurants, you have to distribute Biriyani equally to each of your friends. Otherwise, they will get mad and will not come to visit you for a few days. And what’s even worse, you need to buy Biriyani from consecutive restaurants! That means if you buy from restaurant 2, then you can not skip restaurant 3 and buy from restaurant 4.
Now you have to tell us, how many different ways can you buy Biriyani from restaurants, considering all the constraints mentioned above. Two ways are different, if one of the starting or ending restaurant is different in one of the configurations. Please see the example cases for further explanation.
Input
The first line of input contains an integer T ( 1 ≤ T ≤ 10 ), the number of testcases. Each testcase starts with an integer N ( 1 ≤ N ≤ 105 ), number of shops maintained by rats. The next line contains N positive integers less than or equal to 109, where the i’th integer indicates the amount of Biriyani that the i’th shop produces. After that there is a positive integer K ( 1 ≤ K ≤ 109 ), indicating the number of friends you have.
For around 20 percent of cases, K is at most 2.
Output
For each case, print the number of different ways you can choose restaurants on a line by itself.
Samples
| Input | Output |
|---|---|
1 4 1 2 3 4 2 | 4 |
| Input | Output |
|---|---|
1 2 10 20 2 | 3 |
Explanation
In the first sample, you have K = 2, so you can choose one the following consecutive set of restaurants, ( 1, 2, 3 ) , ( 2 )</b? , ( 4 ) or ( 1 , 2 , 3 , 4 ). For example, if you choose restaurants 1, 2 and 3, then your total amount of Biriyani will be 6, which you can safely distribute equally among your two friends. But if you choose restaurants 2 and 3, you’ll have 5 amount of Biriyani and there is no way of distributing them among your two friends.
In the second sample, you can either choose restaurants 1 or 2 or 1 and 2 both.
