/*input
1
2 4
*/
#include<bits/stdc++.h>
using namespace std;
int dp[55][8][8][8][8];
vector<int> obvious(int ppreAttack)
{
vector<int> ret;
int a = 0;
if((ppreAttack & (1<<0))==0 || (ppreAttack & (1<<2))==0) a |= (1<<1);
if((ppreAttack & (1<<1))==0){
ret.push_back(a | (1<<0));
ret.push_back(a | (1<<2));
}
if(ret.empty()) ret.push_back(a);
return ret;
}
vector<int> allpossible(int now)
{
vector<int> ret;
for(int i = 0; i<8; i++)
{
if((i&now) == now) ret.push_back(i);
}
return ret;
}
pair<int, int> make_Attack(int ppreKnight, int preKnight, int preAttack, int now)
{
pair<int, int> ret = {preAttack, now}; //making {ppreAttack, preAttack}
if((now & (1<<0))) ret.first |= (1<<2);
if(now & (1<<2)) ret.first |= (1<<0);
if((ppreKnight & (1<<0)) || (ppreKnight & (1<<2))) ret.second |= (1<<1);
if(ppreKnight & (1<<1)){
ret.second |= (1<<0);
ret.second |= (1<<2);
}
if((preKnight & (1<<0))) ret.second |= (1<<2);
if(preKnight & (1<<2)) ret.second |= (1<<0);
return ret;
}
int m;
int rec(int col, int ppreAttack, int preAttack, int ppreKnight, int preKnight)
{
if(col==-1) {
if(preAttack==7 && ppreAttack==7)
return 0;
return 1000000007;
}
int &ret = dp[col][ppreAttack][preAttack][ppreKnight][preKnight];
if(ret != -1) return ret; // memoization
ret = 1000000007;
vector<int> vt = obvious(ppreAttack); // the knight positions of this column which is obvious
for(int x : vt)
{
vector<int> all = allpossible(x); // all possible configuration with its obvious configurations
for(int y : all)
{
auto z = make_Attack(ppreKnight, preKnight, preAttack, y); // making attacking configurations of preAttack and this column
ret = min(ret, __builtin_popcount(y) + rec(col-1, z.first, z.second, preKnight, y));
}
}
return ret;
}
int main()
{
int ans[55];
memset(dp, -1, sizeof dp);
for(m = 4; m<55; m++){
ans[m] = 1000000007;
for(int i = 0; i<8; i++)
for(int j = 0; j<8; j++){
auto z = make_Attack(0, i, 0, j); // initial config i and j and attacking config
ans[m] = min(ans[m], __builtin_popcount(i) + __builtin_popcount(j) + rec(m-3, z.first, z.second, i, j));
}
// cout << m << " " << ans[m] << endl;
}
int t;
scanf("%d", &t);
while(t--)
{
int n;
scanf("%d %d", &n, &m);
int res = 0;
if(n==1) res = m;
else if(n==2) {
res = (m/6) * 4;
m%=6;
if(m <= 1) res += m * 2;
else res += 4;
}
else{
if(m==1) res = 3;
else if(m<=4) res = 4;
else res = ans[m];
}
printf("%d\n", res);
}
return 0;
}
LyppbnB1dAoxCjIgNAoqLwoKI2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBkcFs1NV1bOF1bOF1bOF1bOF07CnZlY3RvcjxpbnQ+IG9idmlvdXMoaW50IHBwcmVBdHRhY2spCnsKCXZlY3RvcjxpbnQ+IHJldDsKCWludCBhID0gMDsKCWlmKChwcHJlQXR0YWNrICYgKDE8PDApKT09MCB8fCAocHByZUF0dGFjayAmICgxPDwyKSk9PTApIGEgfD0gKDE8PDEpOwoJaWYoKHBwcmVBdHRhY2sgJiAoMTw8MSkpPT0wKXsKCQlyZXQucHVzaF9iYWNrKGEgfCAoMTw8MCkpOwoJCXJldC5wdXNoX2JhY2soYSB8ICgxPDwyKSk7Cgl9CglpZihyZXQuZW1wdHkoKSkgcmV0LnB1c2hfYmFjayhhKTsKCXJldHVybiByZXQ7Cn0KdmVjdG9yPGludD4gYWxscG9zc2libGUoaW50IG5vdykKewoJdmVjdG9yPGludD4gcmV0OwoJZm9yKGludCBpID0gMDsgaTw4OyBpKyspCgl7CgkJaWYoKGkmbm93KSA9PSBub3cpIHJldC5wdXNoX2JhY2soaSk7Cgl9CglyZXR1cm4gcmV0Owp9CgpwYWlyPGludCwgaW50PiBtYWtlX0F0dGFjayhpbnQgcHByZUtuaWdodCwgaW50IHByZUtuaWdodCwgaW50IHByZUF0dGFjaywgaW50IG5vdykKewoJcGFpcjxpbnQsIGludD4gcmV0ID0ge3ByZUF0dGFjaywgbm93fTsgLy9tYWtpbmcge3BwcmVBdHRhY2ssIHByZUF0dGFja30KCWlmKChub3cgJiAoMTw8MCkpKSByZXQuZmlyc3QgfD0gKDE8PDIpOwoJaWYobm93ICYgKDE8PDIpKSByZXQuZmlyc3QgfD0gKDE8PDApOwoJaWYoKHBwcmVLbmlnaHQgJiAoMTw8MCkpIHx8IChwcHJlS25pZ2h0ICYgKDE8PDIpKSkgcmV0LnNlY29uZCB8PSAoMTw8MSk7CglpZihwcHJlS25pZ2h0ICYgKDE8PDEpKXsKCQlyZXQuc2Vjb25kIHw9ICgxPDwwKTsKCQlyZXQuc2Vjb25kIHw9ICgxPDwyKTsKCX0KCWlmKChwcmVLbmlnaHQgJiAoMTw8MCkpKSByZXQuc2Vjb25kIHw9ICgxPDwyKTsKCWlmKHByZUtuaWdodCAmICgxPDwyKSkgcmV0LnNlY29uZCB8PSAoMTw8MCk7CgoJcmV0dXJuIHJldDsKfQoKaW50IG07CmludCByZWMoaW50IGNvbCwgaW50IHBwcmVBdHRhY2ssIGludCBwcmVBdHRhY2ssIGludCBwcHJlS25pZ2h0LCBpbnQgcHJlS25pZ2h0KQp7CglpZihjb2w9PS0xKSB7CgkJaWYocHJlQXR0YWNrPT03ICYmIHBwcmVBdHRhY2s9PTcpCgkJCXJldHVybiAwOwoJCXJldHVybiAxMDAwMDAwMDA3OwoJfQoKCglpbnQgJnJldCA9IGRwW2NvbF1bcHByZUF0dGFja11bcHJlQXR0YWNrXVtwcHJlS25pZ2h0XVtwcmVLbmlnaHRdOyAgIAoJaWYocmV0ICE9IC0xKSByZXR1cm4gcmV0OyAvLyBtZW1vaXphdGlvbgoKCglyZXQgPSAxMDAwMDAwMDA3OwoJdmVjdG9yPGludD4gdnQgPSBvYnZpb3VzKHBwcmVBdHRhY2spOyAgIC8vIHRoZSBrbmlnaHQgcG9zaXRpb25zIG9mIHRoaXMgY29sdW1uIHdoaWNoIGlzIG9idmlvdXMKCWZvcihpbnQgeCA6IHZ0KQoJewoJCXZlY3RvcjxpbnQ+IGFsbCA9IGFsbHBvc3NpYmxlKHgpOyAgLy8gYWxsIHBvc3NpYmxlIGNvbmZpZ3VyYXRpb24gd2l0aCBpdHMgb2J2aW91cyBjb25maWd1cmF0aW9ucwoJCWZvcihpbnQgeSA6IGFsbCkKCQl7CgkJCWF1dG8geiA9IG1ha2VfQXR0YWNrKHBwcmVLbmlnaHQsIHByZUtuaWdodCwgcHJlQXR0YWNrLCB5KTsgICAvLyBtYWtpbmcgYXR0YWNraW5nIGNvbmZpZ3VyYXRpb25zIG9mIHByZUF0dGFjayBhbmQgdGhpcyBjb2x1bW4KCQkJcmV0ID0gbWluKHJldCwgX19idWlsdGluX3BvcGNvdW50KHkpICsgcmVjKGNvbC0xLCB6LmZpcnN0LCB6LnNlY29uZCwgcHJlS25pZ2h0LCB5KSk7CgkJfQoJfQoJcmV0dXJuIHJldDsKfQoKaW50IG1haW4oKQp7CglpbnQgYW5zWzU1XTsKICAgIAoJbWVtc2V0KGRwLCAtMSwgc2l6ZW9mIGRwKTsKCWZvcihtID0gNDsgbTw1NTsgbSsrKXsKICAgIAlhbnNbbV0gPSAxMDAwMDAwMDA3OwogICAgCWZvcihpbnQgaSA9IDA7IGk8ODsgaSsrKQogICAgCWZvcihpbnQgaiA9IDA7IGo8ODsgaisrKXsKICAgIAkJYXV0byB6ID0gbWFrZV9BdHRhY2soMCwgaSwgMCwgaik7ICAvLyBpbml0aWFsIGNvbmZpZyBpIGFuZCBqIGFuZCBhdHRhY2tpbmcgY29uZmlnCiAgICAJCWFuc1ttXSA9IG1pbihhbnNbbV0sIF9fYnVpbHRpbl9wb3Bjb3VudChpKSArIF9fYnVpbHRpbl9wb3Bjb3VudChqKSArIHJlYyhtLTMsIHouZmlyc3QsIHouc2Vjb25kLCBpLCBqKSk7CiAgICAJfQogICAgCS8vIGNvdXQgPDwgbSA8PCAiICIgPDwgYW5zW21dIDw8IGVuZGw7Cgl9CiAgICAJCQoJaW50IHQ7CglzY2FuZigiJWQiLCAmdCk7Cgl3aGlsZSh0LS0pCgl7CgkJaW50IG47CgkJc2NhbmYoIiVkICVkIiwgJm4sICZtKTsKCQlpbnQgcmVzID0gMDsKCQlpZihuPT0xKSByZXMgPSBtOwoJCWVsc2UgaWYobj09MikgewoJCQlyZXMgPSAobS82KSAqIDQ7CgkJCW0lPTY7CgkJCWlmKG0gPD0gMSkgcmVzICs9IG0gKiAyOwoJCQllbHNlIHJlcyArPSA0OwoJCX0KCQllbHNlewoJCQlpZihtPT0xKSByZXMgPSAzOwoJCQllbHNlIGlmKG08PTQpIHJlcyA9IDQ7CgkJCWVsc2UgcmVzID0gYW5zW21dOwoJCX0KCQlwcmludGYoIiVkXG4iLCByZXMpOwoJfQoJcmV0dXJuIDA7CiAgICAJCn0=