Code:
#include<stdio.h>
#include<string.h>
int main()
{
    char a[3001],b[3001];
    int t,D[2][2005],A,B,LEFT,TOP,CORNER,temp,CURR,PREV;
    scanf("%d",&t);
    getchar();
    while(t--)
    {
              scanf("%s",&a);
              scanf("%s",&b);
              
              A=strlen(a);
              B=strlen(b);
              CURR=0;
              PREV=1;
              for(int i=0;i<B+1;i++)
                      D[CURR][i]=i;
              
              for(int i=1;i<=A;i++)
              {
                     
                      CURR=(CURR+1)%2;
                      PREV=(PREV+1)%2;
                      D[CURR][0]=i;
                      
                      for(int j=1;j<=B;j++)
                      {
                              LEFT=D[CURR][j-1]+1;
                              TOP=D[PREV][j]+1;
                              if(a[i-1]==b[j-1])
                                               CORNER=D[PREV][j-1];
                              else
                                  CORNER=D[PREV][j-1]+1;
                              if(LEFT<TOP&&LEFT<CORNER)           temp=LEFT;
                              else if(TOP<LEFT&&TOP<CORNER)       temp=TOP;
                              else                                temp=CORNER;
                              D[CURR][j]=temp;        
                      }
              }              
            printf("%d\n",D[CURR][B]);    
    }
    return 0;
}