B. Bigger, Bigger, Bigger
time limit per test
1.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given five positive integers: $$$x,y,z,k,d$$$. In each turn, you can choose one of the following two operations:

  • Multiply $$$x$$$ by $$$k$$$ and add $$$d$$$ to $$$y$$$: $$$x = x \times k,~y = y + d$$$;
  • Multiply $$$y$$$ by $$$k$$$ and add $$$d$$$ to $$$x$$$: $$$y = y \times k,~x = x + d$$$;

Your task is to calculate the minimum number of turns required to make $$$x \times y\ge z$$$.

Input

The only line contains five positive integers $$$x,y,z,k,d~(1\le x,y,z,d\le 10^{12},~2\le k\le 10^{12})$$$.

Output

For each set of input data, output a single number — the minimum number of turns required to make $$$x \times y\ge z$$$.

Example
Input
1 2 40 2 2
Output
2