405176: GYM101810 D Magic Sticks

You are given a n × m grid, your goal is to find a group of lines such that the following conditions are met:

1. No two lines are touching.
2. Each cell in the grid has one of its sides covered by at least one line in the group.

A line is a border of a cell in the grid with length 1. Each cell has 4 lines covering every side of it. Every pair of neighboring cells shares a line. Two lines are touching if they meet at their ends.

The size of a group of lines is the number of lines it contains. Your task is to find the minimum size of a group of lines that meet all the conditions above. Can you?

The first line contains an integer T (1 ≤ T ≤ 128) specifying the number of test cases.

Each test case consists of a single line containing two integers n and m (1 ≤ n ≤ 10⁹, 1 ≤ m ≤ 1024), giving a grid of size n × m.

For each test case, print a single line containing the minimum size of a group of lines that meet all the conditions in the statement above.

1
4 4

10