Frozen Ticket Booking

Interview

Time limit1sMemory limit512 MB

Summary

Given a theater with N rows and M seats per row numbered row by row, print the seat number of the fourth seat of row L, or -1 if row L has no fourth seat.

Level: Easy2 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

Jeonghwi is going to a sing-along screening of Frozen 2, the eternal masterpiece and biggest box-office hit of animation.

Jeonghwi likes Elsa of all the Frozen characters so much that he wants to sit in L4, the fourth seat of row L.

However, the theater Jeonghwi is going to represents each seat by a single positive integer, so booking is a hassle.

The theater where Jeonghwi watches Frozen has seats arranged in N rows and M columns.

Seat numbering starts at 1 for the first seat of row A at the top left, increases by one going right, and when it reaches the end it continues from the first seat of row B going right again, then from the first seat of row C going right again, repeating as the numbers increase.

Find the seat number of the fourth seat of row L so that Jeonghwi can grab seat L4 quickly and belt out Show Yourself.

Input

The first line gives the number of test cases T (1 ≤ T ≤ 20).

Each test case occupies one line and gives two positive integers N and M (1 ≤ N ≤ 26, 1 ≤ M ≤ 9). N is the number of rows of seats in the theater, and M is the number of seats in one row.

The image below shows the case N = 4, M = 6.

Output

For each test case, print on one line the seat number of the fourth seat of row L. If the theater has no fourth seat in row L, print -1.

Hint

TMI) The problem setter still has not watched Frozen 2.

Examples2

Example 1
Input
```
1
13 4
```
Expected output
```
48
```
Example 2
Input
```
2
13 5
10 9
```
Expected output
```
59
-1
```