Interviews

Input

The first line contains a single integer $t$ (1 \le t \le 10^4) — the number of test cases.

Each test case consists of a single line containing four integers p, x, y, z (1 \le p,x,y,z \le 10^9) — the number of candidates applying to MathModel Labs, the number of interviewers, the maximum number of interviews one interviewer can attend per day, and the number of interviewers required for a single candidate's interview.

Output

Output the minimum number of days required to interview all $p$ candidates, or print $-1$ if it is impossible.

Examples

Note

In the first test case , the process can be happen as following on just Day $1$ :

1. Interviewers $1$ and $2$ interviews Candidate $1$

2. Interviewers $1$ and $3$ interviews Candidate $2$.

3. Interviewers $2$ and $3$ interviews Candidate $3$.

This arrangement hold two interviewers per meeting , single candidate and a maximum of two interviews per day for an interviewer.

In the second test case, each interviewer can attend interviews with a total of $2$ candidates, so the hiring process finishes in $5$ days.

In the third test case, each interviewer can attend interviews with a total of $1$ candidate, so the hiring process finishes in $9$ days.

In the fourth test case, each interviewer can attend $2$ interviews per day, and each interview requires $3$ interviewers. One valid schedule is:

1. Day $1$: all $3$ interviewers interview Candidate $1$, then all $3$ interviewers interview Candidate $2$.

2. Day $2$: all $3$ interviewers interview Candidate $3$, then all $3$ interviewers interview Candidate $4$.

3. $\dots$

4. Day $10$: all $3$ interviewers interview Candidate $19$, then all $3$ interviewers interview Candidate $20$.

Therefore, it takes $10$ days to finish.

In the fifth test case, it can be shown that it is impossible to interview all candidates.

Scoring

1. Subtask $1$ ($20$ points) : (1 \le p,x,y,z \le 10)

2. Subtask $2$ ($30$ points) : (y=1)

3. Subtask $3$ ($100$ points) : No additional constraints