#include<iostream>#include<string.h>#define SIZE 502using namespace std;int dp[3][SIZE][SIZE];int Max(int x, int y, int z){int tmp = (x > y ? x : y);return tmp > z ? tmp : z;}void initialise(int len1, int len2){for(int i = 0; i != 3; ++i)for(int j = 0; j != len1 + 1; ++j)for(int k = 0; k != len2 + 1; ++k)dp[i][j][k] = -0xfffffff;dp[0][0][0] = dp[1][0][0] = dp[2][0][0] = 0;for(int i = 1; i != len2 + 1; ++i)dp[1][0][i] = -(4 + i);for(int i = 1; i != len1 + 1; ++i)dp[2][i][0] = -(4 + i);}int main(){string str1, str2;int len1, len2, n;cin >> n;while(n--){cin >> str1 >> str2;len1 = str1.size();len2 = str2.size();initialise(len1, len2);for(int i = 1; i != len1 + 1; ++i)for(int j = 1; j != len2 + 1; ++j){int v = ((str1[i - 1] == str2[j - 1]) ? (2) : (-1));dp[0][i][j] = Max(dp[0][i - 1][j - 1] + v, dp[1][i - 1][j - 1] + v, dp[2][i - 1][j - 1] + v);dp[1][i][j] = Max(dp[0][i][j - 1] - 5, dp[1][i][j - 1] - 1, dp[2][i][j - 1] - 5);dp[2][i][j] = Max(dp[0][i - 1][j] - 5, dp[1][i - 1][j] - 5, dp[2][i - 1][j] - 1);}cout << Max(dp[0][len1][len2], dp[1][len1][len2], dp[2][len1][len2]) << endl;}return 0;}
