D. Abu Shehab Private Jet (Easy Version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Note: The only difference between the easy and the medium version is the arrangement of seats.

Abu Shehab travels very often; sometimes he goes to 7alab to see Abu elNoor, and sometimes he goes to Palestine to give them weapons and help them. Meanwhile, Shareefeh stays alone at home.

She reads lots of books, and she was thinking how beautiful this world is. She wants to visit many places like Abu Shehab does. After begging Abu Shehab several times to take her, he finally agreed and booked a trip on a special airplane.

This airplane has a unique seating arrangement: it consists of rows, and each section has three seats. There are a total of n rows.

Shareefeh, observing the passengers boarding, notices a fascinating seating pattern: People seemed to be intentionally leaving empty seats around themselves. Specifically, they avoided sitting in seats directly beside another passenger, even across section boundaries (left and right across the aisle).

Abu Shehab informs her that $$$m$$$ people are boarding. Since she thinks people don't like sitting next to each other, she defines the happiness of the plane as the total number of adjacent seat pairs where exactly one seat is occupied and the other is empty.

What is the maximum possible happiness of the plane across all possible ways of seating $$$m$$$ people on a plane with $$$n$$$ rows?

Input

The first line of input will contain one integer $$$T$$$ $$$(1 \leq T \leq 10^5)$$$, which is the number of test cases.

Each test case contain one line,

The only line of input will contain two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n \leq 10^8)$$$, $$$(1 \leq m \leq 10^8)$$$, which represent the number of rows in the airplane and the number of people boarding, respectively.

Output

Each test case print contain one line which is the maximum happiness or print $$$-1$$$ when the jet does not fit $$$m$$$ peoples.

Example
Input
4
15 5
10 17
55 55
6 75
Output
10
20
110
-1
Note

Counting empty seats means for every person you count the empty adjacent seats to the person's left and right and you can count the same empty seat, for different people, multiple times.