Dad's Card Trick

Time limit1sMemory limit256 MB

Summary

For each test case with N cards and K face up, compute the fewest moves and flips that force both decks to hold equal face-up counts whatever the layout.

Level: Hard8 of 10
Topics: Math, Combinatorics
Solved: No attempts yet

Problem

You show off card tricks so often that your family is worn out. To put a stop to it, your dad picks a trick he believes you cannot do.

He blindfolds you and hands you a deck of $N$ cards. He tells you that exactly $K$ of them are face up, but not which ones. A second deck starts out empty.

Here is the goal. After the last operation the two decks have to hold the same number of face-up cards. That number does not have to be $K$ . You are blindfolded and cannot see the arrangement, so one sequence of operations has to succeed for every possible initial arrangement of the face-up cards.

You may perform the following two operations in any order, any number of times.

Move one card from one deck to the other.
Flip one card in either deck. A face-up card becomes face down, and a face-down card becomes face up.

To impress your dad you accepted the challenge, and you decided to find the shortest possible sequence of operations. Write a program that computes its length.

Input

The first line contains a single integer $T$ , the number of test cases. Each of the following $T$ lines contains two integers $N$ and $K$ , separated by a space.

$1 \le T \le 20$
$1 \le K \le N \le 1000$

Output

For each test case, print on one line the minimum number of operations needed to reach the goal. If the goal cannot be reached, print $-1$ instead.

Examples3

Example 1
Input
```
3
2 1
3 2
10 3
```
Expected output
```
2
3
6
```
Example 2
Input
```
1
1 1
```
Expected output
```
1
```
Example 3
Input
```
6
2 2
3 3
4 4
5 5
6 6
7 7
```
Expected output
```
1
2
2
3
3
4
```