#include <bits/stdc++.h>
#define pc(x) __builtin_popcount(x)
using namespace std;
int dx[8] = {2 , 2 , -2 , -2 , 1 , 1 , -1 , -1};
int dy[8] = {1 , -1 , 1 , -1 , 2 , -2 , 2 , -2};
int G[5][5] , att[5][5];
void make(int &a , int &b , int &c){
    G[0][0] = (a & 1); G[1][0] = (a & 2); G[2][0] = (a & 4);
    G[0][1] = (b & 1); G[1][1] = (b & 2); G[2][1] = (b & 4);
    G[0][2] = (c & 1); G[1][2] = (c & 2); G[2][2] = (c & 4);
    for(int j = 0 ; j < 3 ; j++)
        for(int i = 0 ; i < 3 ; i++)
            G[j][i] = min(G[j][i] , 1);
    for(int x = 0 ; x < 3 ; x++){
        for(int y = 0 ; y < 3 ; y++){
            att[x][y] = G[x][y];
            for(int d = 0 ; d < 8 ; d++){
                int nx = x + dx[d] , ny = y + dy[d];
                if(nx < 0 || ny < 0 || nx > 2 || ny > 2) continue;
                att[x][y] |= G[nx][ny];
            }
        }
    }
    a = att[0][0] + (att[1][0]<<1) + (att[2][0]<<2);
    b = att[0][1] + (att[1][1]<<1) + (att[2][1]<<2);
    c = att[0][2] + (att[1][2]<<1) + (att[2][2]<<2);
}
int dp[51][8][8][8][8];
int T , R , C;
int inf = (1<<20);
int calc(int col , int patt , int att , int pmask , int mask){
    if(col == C + 1){
        if(patt == 7 && att == 7) return 0;
        else return inf;
    }
    int &ret = dp[col][patt][att][pmask][mask]; if(ret != -1) return ret;
    ret = inf;
    for(int nxt = 0 ; nxt < 8 ; nxt++){
        int a = pmask , b = mask , c = nxt;
        make(a , b , c);
        a |= patt , b |= att;
        if(a == 7)
            ret = min(ret , pc(nxt) + calc(col + 1 , b , c , mask , nxt));
    }
    return ret;
}
int main(){

    cin>>T;
    while(T--){
        memset(dp , -1 , sizeof(dp));
        cin>>R>>C;
        if(R > C) swap(R , C);
        if(R == 1){
            cout<<C<<endl;
            continue;
        }
        if(R == 2){
            cout<< ( C / 6 ) * 4 + min( C % 6 , 2 ) * 2<<endl;
            continue;
        }
        int ans = inf;
        for(int j = 0 ; j < 8 ; j++){
            for(int i = 0 ; i < 8 ; i++){
                int a = j , b = i , c = 0;
                make(a , b , c);
                ans = min(ans , pc(j) + pc(i) + calc(3 , a , b , j , i));
            }
        }
        cout<<ans<<endl;
    }
}