ACM International Collegiate Programming Contest, Amman Collegiate Programming Contest (2018) |
---|
Закончено |
You are given a n × m grid, your goal is to find a group of lines such that the following conditions are met:
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 ≤ 109, 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
Название |
---|