RAIN3  Rain
Doctor Jones is a famous archeologist. He did some research on the Tiribaki Islands recently. His most famous discovery was the Meteoronome  a machine with a yellow button used by the Tiribakian highest priest to predict the weather. The Meteoronome had been set up by the gods at the Beginning of Time. Tiribakians pressed the button every day. As a result, the Meteoronome produced a number  the expected rainfall in millimetres for the next day. More precisely, after i button hits (counted since the Beginning of Time) Meteoronome gives the expected rainfall for the day i since the Beginning of Time.
Unfortunately, the Meteoronome has not been used for several thousands of years and nobody knows how many steps should be performed to reach the current date. Researchers have spent a lot of effort to find out how the Meteoronome works. A mathematical model has been proposed: The Meteoronome is initialized by a pair of integers, s[0] and t[0]. For the ith step, the Meteoronome computes the values
s[i] = (78901 + 31*s[i1]) mod 699037 t[i] = (23456 + 64*t[i1]) mod 2097151
The output of the ith step is the number
a[i]=(s[i] mod 100 + 1) * (t[i] mod 100 + 1)
Doctor Jones's friend, Ms. Linda Watson, is now planning a holiday on Tiribaki Islands. She would like to stay there as long as possible but she hates the rain. She can stand no more than M millimetres of rainfall during her entire stay on Tiribaki.
Doctor Jones wants to help his friend and to compute the longest period which she can safely stay on Tiribaki. He simulated N steps of the Meteoronome. This way, he obtained a sequence of numbers a[1],a[2],...,a[N] which represent predictions for N subsequent days. Now he wants to find the largest K such that for each period of at most K subsequent days from day i to day j the sum of the predictions a[i]+a[i+1]+...+a[j] is less than or equal to M. Linda can be sure that if she stays on Tiribaki for at most K days, she can endure the rain (provided that N is large enough).
Input specification
The input file consists of several blocks of data. The first line of the input file contains the number of blocks. Each block contains four integers delimited by whitespace: s[0], t[0]  the initial values for the Meteoronome, N (1<= N <=1500000) the length of the sequence and M  the maximum sum of a subsequence. All the input data fits into 32bit signed integer.
Output specification
The output file contains one line for each block of input data. In this line there is a single integer K as specified above.
Example
Input file: 1 123456 123456 10 10000 Output file: 2
Note, that the sequence produced by Meteoronome for this input file is 4664,1248,267,4900,837,4048,990,6935,1155,490. No subsequence of length 2 has sum greater than 10000 and there are subsequences of length 3 with greater sum.
hide comments
dwij28:
20161015 22:18:57
I am using binary search and getting a TLE. Any hints on optimization ?


Necromancer:
20160325 09:52:42
Wrong Tag.. 

Shashank Tiwari:
20151107 22:14:35
The question says to find such maximum 'K' length such that


Sumit Paroothi:
20150802 07:53:25
use long long wisely.. 
Added by:  Fudan University Problem Setters 
Date:  20071201 
Time limit:  0.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: C99 ERL JSRHINO 
Resource:  IPSC 1999 