题目描述

给定 $n$ 枚有两面（朝下或朝上）的硬币，其中有 $s$ 枚朝上，其余的朝下。 你可以操作硬币任意次（包括零次）；在每次操作中，你应任选恰好 $k$ 枚硬币进行翻转（朝上变为朝下，反之亦然）。 你的目标是将朝上的硬币数量从 $s$ 变为 $t$。输出所需的最少操作次数或报告无解。

输入格式

第一行包含测试用例的数量 $T$ （$1 \le T \le 2\times10^5$）。每个测试用例占一行，包含四个整数$n,k,s,t$。

满足$1 \le k \le n \le 10^9, 0 \le s,t \le n$。

输出格式

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

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

输入输出样例 #1

输入 #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

1
5
15
0
1
-1
43850658
-1