F. Mega Polynomial
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two polynomials $$$f(x) = Ax + B$$$ and $$$g(x) = Cx^n + Dx^{n-1}$$$. Your task is to find the minimum integer $$$k$$$, such that $$$g^{(k)}(x)$$$ is divisible by $$$f(x)$$$.

Here, $$$g^{(k)}(x)$$$ represents taking the derivative of $$$g(x)$$$ exactly $$$k$$$ times.

Formally,

  • $$$g^{(0)}(x) = g(x)$$$,
  • $$$g^{(k)}(x) = \frac{d}{dx} \left( g^{(k-1)}(x) \right)$$$ for $$$k \geq 1$$$,

and

  • $$$\frac{d}{dx} \left( Ex^m + Fx^{m-1} \right) = mEx^{m-1} + (m-1)Fx^{m-2}$$$ for $$$m \gt 1$$$,
  • $$$\frac{d}{dx} \left( Gx \right) = G$$$,
  • $$$\frac{d}{dx} \left( G \right) = 0$$$,

where $$$E$$$, $$$F$$$, and $$$G$$$ are constants.

For example, for $$$g(x) = x^3 + 3x^2$$$, we can find that:

  • $$$g^{(1)}(x) = 3x^2 + 6x$$$,
  • $$$g^{(2)}(x) = 6x + 6$$$,
  • $$$g^{(3)}(x) = 6$$$,
  • $$$g^{(4)}(x) = 0$$$.

We say that a polynomial $$$P_1(x)$$$ is divisible by $$$P_2(x)$$$ if and only if there exists a polynomial $$$Q(x)$$$ such that $$$P_1(x) = Q(x)P_2(x)$$$, where the coefficients of $$$Q$$$ are integers.

Input

The first line contains one positive integer $$$t$$$ ($$$1\leq t \leq 10^5$$$) — the number of test cases.

Each test case consists of one line which contains $$$5$$$ integers $$$A,B,C,D,n$$$ ($$$1\leq A,B,C,D,n\leq 2\cdot 10^5$$$).

Output

For each test case, output the minimum integer $$$k$$$, such that $$$g^{(k)}(x)$$$ is divisible by $$$f(x)$$$.

Example
Input
6
1 2 2 4 1
4 2 3 3 4
2 4 1 3 3
2 1 5 2 4
131296 123463 91609 133724 142208
172458 127836 190471 141192 190476
Output
0
2
4
5
50599
190477
Note

In the first test case, $$$f(x)=x+2$$$ and $$$g(x)=2x+4$$$. We can see that $$$g^{(0)}(x)$$$ is divisible by $$$f(x)$$$ because $$$g^{(0)}(x)=g(x)=2x+4=2 \cdot f(x)$$$. So, the answer is $$$0$$$.

In the second test case, $$$f(x)=4x+2$$$ and $$$g(x)=3x^4+3x^3$$$. We can see that $$$k=2$$$ is the minimum integer such that $$$g^{(k)}(x)$$$ is divisible by $$$f(x)$$$ because $$$g^{(2)}(x)=36x^2+18x=9x \cdot f(x)$$$.

In the third test case, $$$f(x)=2x+4$$$ and $$$g(x)=x^3+3x^2$$$. We can see that $$$k=4$$$ is the minimum integer such that $$$g^{(k)}(x)$$$ is divisible by $$$f(x)$$$ because $$$g^{(4)}(x)=0=0 \cdot f(x)$$$.

Note that although $$$g^{(1)}(x)=3x^2+6x=\frac{2}{3}x \cdot f(x)$$$, $$$g^{(1)}(x)$$$ is not divisible by $$$f(x)$$$ since $$$\frac{2}{3}$$$ is not an integer.