题目描述

你正在管理一个老旧的线性机械硬盘，该硬盘被划分为 $N$ 个连续的扇区（编号从 $1$ 到 $N$）。

由于文件系统的特殊分配机制，第 $i$ 个扇区中存储的数据量为 $C \times i$ 字节（其中 $C$ 是系统簇大小的常数）。例如，当 $C = 2$ 时，第 $1$ 到 $4$ 个扇区的数据量分别为 $2, 4, 6, 8$ 字节。

现在，你需要从这块硬盘中恰好读取 $W$ 字节的数据来进行恢复。为了最小化磁头的寻道损耗，你只能向硬盘发送“读取指令”。每次指令可以指定一个连续的扇区区间 $[l, r]$，并读取该区间内的所有数据。

请问，要读取恰好 $W$ 字节的数据，最少需要发送多少次读取指令？注意：每个扇区最多只能被读取一次。如果无论如何也无法凑出恰好 $W$ 字节，请输出 $-1$。

输入格式

第一行包含一个整数 $T$，表示测试用例的组数。

接下来 $T$ 行，每行包含三个整数 $N, C, W$，相邻整数之间用空格隔开。

输出格式

对于每组测试用例，输出一行一个整数，表示最少的读取指令次数。如果无法完成，输出 $-1$。

3
4 2 10
4 2 16
4 2 7

1
2
-1

提示

【评测用例规模与约定】

对于 $30\%$ 的评测用例，$1 \le N \le 1000$，$T = 2$。

对于所有的评测用例，$1 \le N \le 10^5$，$2 \le T \le 10$，$1 \le C \le 100$，$0 \le W \le 10^9$。