B.Long Drive On 14th
Tag(s):
No tags
Problem
Editorial
Analytics

Abhi the smartest boy of IIIT-A is going for a long drive on the holy ocassion of Valentines Day with his GF and if he will drive for $x$ hours then he will get $h$ amount of happiness level. Here $h= a* x^{k1} + b* x^{k2}$  where  $a, b, k1, k2$ are non negative integers. Obviously , Abhi wants to be as much happy as possible but Sonu has became jealous from Abhi . That is why,  Sonu can't bear the happiness level of Abhi more than $M$ . As, Abhi is a gentle man and having a golden heart . So, he can't make Sonu angry due to his own happiness and finally he decided to drive only for that amount of hours which Sonu can bear. Abhi asked to Kalyan for calculating the maximum amount of hours $x$ ( an integer) such that he may enjoy Valentines Day without making Sonu angry . But, Kalyan is busy in creating real life programming problems for you. So, Kalyan assigned this task to you.

In every testcases you have given $a, b, k1, k2$ and $M$  and you have to tell the maximum value of integer $x$ such that Sonu shouldn't become angry with Abhi. If the maximum value of $x$ is greater than or equal to 105 then print "Love is immortal" otherwise print the maximum $x$ .

Input

The first line of the input contains a single integer $T$ denoting the number of test cases.

The description of $T$ test cases follows.

Only one line in each testcase containing $a, b, k1, k2$ and $M$ respectively.

Output

For each testcase print the answer.

Constrains

1 <= $T$ <= 106

0 <= $a, b$ <= 10

0 <= $k1, k2$ <= 3

0<= $M$ <= 1018

SAMPLE INPUT
2
0 2 1 2 15
1 1 1 1 16
SAMPLE OUTPUT
2
8
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...