Bob is a businessman. He always stays at city A or city B.
Assume Bob stays at city A today , and we can use a transition matrix P to infer the probability of at which city will Bob stays tomorrow.
e.g.
Let VnT = [ va , vb ]Vn is a 2 by 1 column vector.
va denotes the probability that Bob stays at city A on n-th day,
vb denotes the probability that Bob stay at city B on n-th day.
After 1 day, the probability should be represented as Vn+1 , where Vn+1 = Vn * P.
P is a 2 by 2 square matrix, representing the transition probability:
P = ┌ p1 p2 ┐
└ p3 p4 ┘
As time passes, the probability of Bob staying at city A will decrease.
After n days, the probability of Bob staying at city A will smaller than or equal to a target value T.
The question is :
Suppose that Bob stays at city A today ( va = 1 , vb = 0)
How many days do we need to make va smaller than or equal to the target value T ?
Namely , n = ?
Note :
The test case will make va monotonically decrease .
助教出的測資一定會讓 va 隨著時間增加而逐漸遞減
There are multiple testcases in the input.
The first line contains a integer N, indicating the number of testcases.
You can use this format in your code:
int i , N;
scanf("%d",&N);
for(i=0;i<N;i++){
// your code to deal with each testcase
}
The following lines are testcases.
For each testcase, there are 5 floating points in a line.
The 1st ~ 4th floating points (p1, p2, p3, p4) are the elements in trasition matrix P.
The 5th floating point is the target value T.
For each testcase.
Output integer n that tell us how many days should we take to reach the target probability.
And add a '\n' at the end of each output.