Description
Domo is a brilliant dog. When he feels full, he will be happy.
Every day, he gets food from his breeder with a certain rule as follow:
f(n) = f(n - 1) + f(n - 3), if n > 3, on which f(N) describes the food Domo can get on the N-th day.
One day, Domo realizes that if he stores these foods for days, it will be lots of food that he can eat all of them at once to prevent from hungry!
Given the food that Domo can get from the first day to the third day and an integer P, please find that on which day the total of food that Domo gets will equal or greater than P.
For example (refer sample I/O):
For the first test case, we accumulate 10 foods on day 4 (1, 2, 3, 4 foods on day 1 to day 4, respectively).
For the second test case, we accumulate 7 foods on day 2.
If Domo can not prevent from being hungry, he will lay on the sofa so that you can't find a place to sit.
Input
The first line contains an integer T (1 ≤ T ≤ 10) - the number of tasks you need to solve.
For the following T line, each line contains four integer numbers f(1), f(2), f(3), and P.
(1 ≤ f(1), f(2), f(3) ≤ 1000, 1 ≤ P ≤ 108)
Output
For each task case, output how many days Domo needs to get a certain amount of food, then print a newline after every task.
Note that it's guaranteed that the expected output on each task will not exceed 100!