纠缠硬币翻转

时间限制：1000MS 512MB

题目描述

现有 $n$ 枚分正反两面的硬币，初始 $s$ 枚正面朝上，其余 $n-s$ 枚反面朝上。

你可以对这些硬币进行任意次操作（包括0次）：在每次操作中，你应任选恰好$k$ 枚硬币进行翻转（正面朝上变为反面朝上，反之亦然）。

你的目标是将正面朝上的硬币数从 $s$ 变为 $t$ 。输出所需的最少操作次数或报告无解。

输入描述

第一行含仅一个正整数 $t$ ($1 \leq t \leq 2 \times 10^5$)，代表测试用例的数量。测试用例格式如下：

每个测试用例仅占一行，含四个整数 $n,k,s,t$ ($1 \leq k \leq n \leq 10^9,0 \leq s,t \leq n$)，含义如上。

输出描述

对于每个测试用例，输出仅占一行：

如果有解，输出一个整数表示最少的操作次数；否则输出-1表示无解。

输入样例

8
8 3 4 7
9 7 1 0
16 15 1 0
4 2 3 3
6 6 2 4
7 6 2 5
98257693 98257692 24 43850682
98257693 98257692 24 43850681

输出样例

1
5
15
0
1
-1
43850658
-1

提示

对操作的进一步解释：

设硬币总数为 $n$ ，现正面朝上的硬币数量为 $c$ ，你在该步操作中选择了 $a$ 枚正面朝上的硬币和 $b$ 枚反面朝上的硬币进行翻转，则应有 $0 \le a \le c , 0 \le b \le n-c$ 和 $a+b=k$ ，且操作后正面朝上的硬币数变为 $c-a+b$ 。

比如，当 $n=7,k=3,c=5$ 时，$a$ 可以取 $1/2$ 使 $c$ 依次变为 $6/4$ ，但不能取 $3$ 及以上的整数 (正面朝上的硬币不够用) 或 $0$ (反面朝上的硬币不够用)。

当然，$a$ 和 $b$ 都是整数。