#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n, m;
cin>>n>>m;
int dp[2][m];
for(int j = 0; j < m; j++)
{
dp[0][j] = dp[1][j] = 1;
}
for(int i = 1; i < n; i++)
{
for(int j = 1; j < m; j++)
{
// dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1];
// i = 1 since 1 is the current row, so i-1 = 0
dp[1][j] = dp[0][j] + dp[1][j-1] + dp[0][j-1];
}
for(int j = 1; j < m; j++)
{
// copying the 1th row to 0th row
dp[0][j] = dp[1][j];
}
}
cout<<dp[1][m-1]<<"\n";
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbWFpbigpCnsKCWludCB0OwoJY2luPj50OwoJd2hpbGUodC0tKQogICAgewoJCWludCBuLCBtOwoJCWNpbj4+bj4+bTsKCgkJaW50IGRwWzJdW21dOwoJCWZvcihpbnQgaiA9IDA7IGogPCBtOyBqKyspCiAgICAgICAgewoJCQlkcFswXVtqXSA9IGRwWzFdW2pdID0gMTsKICAgICAgICB9CgoJCWZvcihpbnQgaSA9IDE7IGkgPCBuOyBpKyspCgkJewoJCQlmb3IoaW50IGogPSAxOyBqIDwgbTsgaisrKQoJCQl7CgkJCSAgICAvLyBkcFtpXVtqXSA9IGRwW2ktMV1bal0gKyBkcFtpXVtqLTFdICsgZHBbaS0xXVtqLTFdOwoJCQkgICAgLy8gaSA9IDEgc2luY2UgMSBpcyB0aGUgY3VycmVudCByb3csIHNvIGktMSA9IDAKCQkJCWRwWzFdW2pdID0gZHBbMF1bal0gKyBkcFsxXVtqLTFdICsgZHBbMF1bai0xXTsKCQkJfQoKCQkJZm9yKGludCBqID0gMTsgaiA8IG07IGorKykKICAgICAgICAgICAgewogICAgICAgICAgICAJLy8gY29weWluZyB0aGUgMXRoIHJvdyB0byAwdGggcm93CiAgICAgICAgICAgICAgICBkcFswXVtqXSA9IGRwWzFdW2pdOwogICAgICAgICAgICB9CgkJfQoKCQljb3V0PDxkcFsxXVttLTFdPDwiXG4iOwoJfQoJcmV0dXJuIDA7Cn0=