Scube is passionate about equations,but his passion drove him crazy which got his friend Killcode worried. In order to cure him Killcode decided to hide all his books at different houses in the neighborhood. In time Scube got cured and asked back for his books but unluckily Killcode forgot the houses where the books were hidden. Fortunately Killcode already created an equation in case he forgot the location of the books.
The equation Killcode created was G(x)=A(x^3)+B(x^2)+C(x)+D=k. Where a,b,c,d are prime numbers and k can be any positive integer value. Inserting the values of a,b,c,d and k (which killcode already has),the task is to find the maximum value of x which satisfies the condition LHS<=RHS.
If an x satisfies the above condition, then there exists a book at house number x.
Since the list of prime numbers and k that Killcode has is very big,help Killcode write a program to find the location of the books.

Input
The first line of the input contains a single integer T denoting the number of test cases. each test case consists of a single line containing 5 space seperated positive numbers a, b, c, d, K.
Output
Output an integer x which denotes the house number where a book is present.
Constraints
1 <= t <= 10^5
a,b,c,d belong to a set of prime numbers such that G(x) would never exceed 10^18
x >= 0
1 <= K <=10^18