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<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<string>
typedef long long ll;
using namespace std;
#define maxn 2000005
#define inf 0x3f3f3f3f
const long long int mod = 1e9 + 7;
ll read() {
ll x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch>'9') {
if (ch == '-') {
f = -1;
}
ch = getchar();
}
while (ch >= '0'&&ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
ll quickpow(ll a, ll b) {
ll ans = 0;
while (b > 0) {
if (b % 2)ans = ans * a;
b = b / 2;
a = a * a;
}
return ans;
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a%b);
}
bool cmp(int a, int b) {
return a > b;
}
int main() {
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
ll n, m;
cin >> n >> m;
if (n == m) {
if (n % 2 == 0) {
cout << n * (n + 1) / 2 << endl;
}
else {
cout << n * (n + 1) / 2 << endl;
}
}
else {
ll minn;
if (n % 2 == 0 && m % 2 == 0) {
minn = min(n / 2 * (m + 1), m / 2 * (n + 1));
//minn = min(minn, );
cout << minn << endl;
}
else if (n % 2 == 1 && m % 2 == 1) {
minn = min((n + 1) / 2*m, (m + 1) / 2*n);
//minn = min(minn, );
cout << minn << endl;
}
else if (n % 2 == 1 && m % 2 == 0) {
minn = min(m / 2 * (n / 2+1) + (m / 2 + 1)*(n / 2), m / 2*(n+1));
//minn = min(minn, );
cout << minn << endl;
}
else if (m % 2 == 1 && n % 2 == 0) {
minn = min((m / 2+1) * n / 2 + (m / 2 )*(n / 2 + 1), n*(m+1) / 2);
// minn = min(minn, );
cout << minn << endl;
}
}
}
}