You are given a n × m grid, your goal is to find a group of lines such that the following conditions are met:
No two lines are touching.
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?
Input
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.
Output
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.
Example
Input
1
4 4
Output
10
找到规律即可解决,注意long long ;(试过会炸int
#include
#include
#include
#include
#include
#include
#include
#include
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.e1idc.net