Hanbyeol, who failed the Mathematics 2 final exam and received a grade of B0, is said to be singing the song "Sign is B0" at the recently opened KSA Yeji Hall.

"Anata no aidoru Sain wa B0!"

Hanbyeol starts dancing to the rhythm on the grid of dimension $(N+1) \times (N+1)$.

Given integers $A$, $B$, $C$, and $N$, let $M_{i,j}$ be the coefficient of $x^{i}y^{j}$ for the coefficients of $(Ax+By+C)^{N}$. Hanbyeol dances on the grid by following the given rules, starting from cell $(0,0)$.

1. If $M_{i,j+1}$ is greater than or equal to $M_{i,j}$, Hanbyeol can move from $(i,j)$ to $(i,j+1)$.
2. If $M_{i+1,j}$ is greater than or equal to $M_{i,j}$, Hanbyeol can move from $(i,j)$ to $(i+1,j)$.

Print the length of the longest path that can be moved. The length of the path is equal to the number of times Hanbyeol moves.

Input

Each test contains multiple test cases. The first line contains an integer $T$, the number of test cases. The description of the test cases follows.

The first line of each test case contains four space-separated integers $A$, $B$, $C$, and $N$.

Output

For each test case, print the longest possible length of any path on the grid that Hanbyeol can move.

Constraints

• $1 \leq T \leq 100$
• $1 \leq A, B, C, N \leq 10^{9}$

Scoring

Examples

Input 1

1
1 1 1 2

Output 1

2

Note

This is an illustration of Hanbyeol's possible path for the given example.