Curious case of Vatsan Mama

All submissions for this problem are available.
Guru prakash, Sabari and Srivatsan have recently qualified to participate in World Finals of International Chess Tournament to be held in Yekaterinburg, Russia. Being new with the ruble currency, they wish to familiarize themselves with the coins(kopeks). So they decide to play a game. As usual Srivatsan being the kind guy he decides to be the referee while the other two play the game. He creates n piles numbered 0,1,..n1(He places a board next to each pile denoting its number). In each pile he keeps c_i coins initially.
The rules of the games are as follows:
 For each pile Srivatsan sets an upper limit P_i

In any turn, a player can add atmost floor((P_ic_i)/idx) coin to a pile numbered i.
idx is defined as i%K + 1. This value of K is initially decided by Srivatsan.
So if K = 3, idx= 0%3+1 for pile 0, idx = 1%3 + 1 for pile 1 and so on.
 If a particular player is not able to add coin to any pile, the game stops and the other player wins.
Guru prakash being a muscular fellow, Sabari fears him and lets him start the game. But Guru prakash has some evil ideas. He doesn't want Sabari to win since he brags a lot. He also knows that Srivatsan can be quite lazy and will sometimes not concentrate on the game. In that mean time, Guru prakash can eliminate some of the piles in the game such that he can ensure his win. But since, removing piles in middle will leave holes, Guru has devised a strategy. He decided to remove only piles in the beginning and in the end (if atall he decides to remove). Hence, the remaining piles will form a continuous segment of the original arrangement. Now he wants to know how many ways can he perform this so that he will always win.
Note both of them are smart people and they always play optimally
Input
Input description.
 The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
 The first line of each test case contains two integers N, K denoting the number of piles and the K value used in calculating idx respectively. The second line contains N spaceseparated integers C_{1}, C_{2}, ..., C_{N} denoting the number of coins placed by Srivatsan in each pile.
The third line contains N spaceseparated integers P_{1}, P_{2}, ..., P_{N} denoting the upper limits given by Srivatsan for each pile.
Output
Output description.
 For each test case, output a single integer telling the number of Guru prakash can remove piles as described above.
Constraints
 1 ≤ T ≤ 10
 1 ≤ N ≤ 10000
 1 ≤ K ≤ 10
 1 ≤ C_i ≤ P_i≤ 10^17
Example
Input: 1 3 5 1 2 3 2 6 7 Output: 5
Explanation
There are six ways in which guru can remove piles
{1},{3},{1,2},{2,3},{1,3},null.
null implies not removing any pile.
Removing {1,2} alone leaves the game such that for optimal moves of both, Guru prakash loses.
Author:  karthikabinav 
Tags  karthikabinav 
Date Added:  31122013 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, GO 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 