Problem Description

You are managing an old linear mechanical hard drive, which is divided into $N$ consecutive sectors (numbered from $1$ to $N$).

Because of a special allocation rule of the file system, the amount of data stored in sector $i$ is $C \times i$ bytes (where $C$ is a constant representing the system cluster size). For example, when $C = 2$, the data sizes in sectors $1$ to $4$ are $2, 4, 6, 8$ bytes.

Now you need to read exactly $W$ bytes of data from this hard drive for recovery. To minimize head-seeking cost, you are only allowed to send “read commands” to the drive. Each command can specify a continuous sector interval $[l, r]$ and read all data in that interval.

Find the minimum number of read commands needed to read exactly $W$ bytes. Note: each sector can be read at most once. If it is impossible to make the total exactly $W$ bytes, output $-1$.

Input Format

The first line contains an integer $T$, representing the number of test cases.

The next $T$ lines each contain three integers $N, C, W$, separated by spaces.

Output Format

For each test case, output one integer per line, representing the minimum number of read commands. If it is impossible, output $-1$.

3
4 2 10
4 2 16
4 2 7

1
2
-1

Hint

Constraints and Notes

For $30\%$ of the test cases, $1 \le N \le 1000$, and $T = 2$.

For all test cases, $1 \le N \le 10^5$, $2 \le T \le 10$, $1 \le C \le 100$, $0 \le W \le 10^9$.

Translated by ChatGPT 5