20220209 - 出入条

Time Limit

1000 毫秒

Memory Limit

128 MB

通过次数

1

提交次数

1

n名同学需要进入校园,但他们发现只带了m张进出条,于是他们先让m人进去,而后1人带m张出入条出来,如此往复直到所有人都进入校园。每次打开校门可以进或出若干人并产生一条开门记录,所有人都进入校园共产生多少条开门记录?

Input

第一行,一个整数t

接下来t行,每行两个整数n,m

对于100%的数据:

1 \le t \le 10^5

1 \le m \le n \le 10^9

Output

t行,每行一个整数,表示开门记录多少条。若当前行的n,m无法全部进入学校,当前行输出-1。

Examples

Input

3
6 3
10 10
10 1

Output

5
1
-1