#include <bits/stdc++.h>
#include <sys/resource.h>

using namespace std;

const int DEBUG = false;

#define FOR(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define REP(i,n) FOR(i,0,n)

void print(vector<int> v) {
  for (auto x: v) cerr << x << " "; cerr << endl;
}

const int MAXN = (int) 1e5;
const int MAX = MAXN + 10;
const int LN = 18;

vector<int> g[MAX];
int n, Q, parent[MAX], DP[MAX][LN], L[MAX], visited[MAX];

// Returns lowest common ancestor of two nodes
int lca(int u , int v){
    if(L[u] < L[v]) swap(u,v);
    for(int i = LN - 1 ; i >= 0 ; i--){
      if( L[u] - (1 << i) >= L[v] )
        u = DP[u][i];  
    }
    
    assert(L[u] == L[v]);
    if(u == v) return u;
    
    for(int i = LN - 1 ; i >= 0 ; i--){
      if(DP[u][i] != DP[v][i])
        u = DP[u][i], v = DP[v][i];
    }
    
    assert(DP[u][0] == DP[v][0]);
    return DP[u][0];
}

int bestPath[MAX], secondBestPath[MAX];
int upAnswer[MAX], downAnswer[MAX];

// Set up stuff
void dfs(int u, int p){
  visited[u] = true;
  parent[u] = p;
  for(int i = 0 ; i < g[u].size() ; i++){
    int v = g[u][i];
    if(v == p) {
      assert(visited[v]);
      continue; // Don't go back up!
    }
    
    assert(!visited[v]);
    L[v] = L[u] + 1;
    dfs(v, u);

    if (bestPath[v] + 1 >= bestPath[u]) {
      secondBestPath[u] = bestPath[u];
      bestPath[u] = bestPath[v] + 1;
    } else {
      secondBestPath[u] = max(secondBestPath[u], bestPath[v] + 1);
    }
    downAnswer[v] = bestPath[v];
  }
}

void dfs2(int u, int p) {
  for (int v: g[u]) {
    if (v != p) {
      int len = bestPath[u];
      if (bestPath[v] + 1 == bestPath[u]) {
        len = secondBestPath[u];
      }
      upAnswer[v] = max(len, upAnswer[u] + 1);
      dfs2(v, u);
    }
  }
}

void setup() {
  memset(visited, 0, sizeof(visited));
  memset(L, 0, sizeof(L));
  memset(parent, -1, sizeof(parent));
  memset(bestPath, 0, sizeof(bestPath));
  memset(secondBestPath, 0, sizeof(secondBestPath));
  memset(downAnswer, 0, sizeof(downAnswer));

  cerr << "first dfs started" << endl;

  dfs(0, 0);
  for (int i = 0; i < n; i++) {
    assert(visited[i] == true);
  }
  for(int j = 1 ; j < LN ; j++)
    for(int i = 0; i < n ; i++)
      DP[i][j] = 0;
  for (int i = 0; i < n; i++) {
    DP[i][0] = parent[i];
  }
  for(int j = 1 ; j < LN ; j++)
    for(int i = 0; i < n ; i++)
      DP[i][j] = DP[DP[i][j-1]][j-1];

  memset(upAnswer, 0, sizeof(upAnswer));
  upAnswer[0] = -1; // to adjust the first term properly.
  dfs2(0, 0);
  cerr << "second dfs ended" << endl;

  if (DEBUG) {
    cerr << "bestPath" << endl;
    for (int i = 0; i < n; i++) {
      cerr << bestPath[i] << " ";
    }
    cerr << endl;

    cerr << "secondBestPath" << endl;
    for (int i = 0; i < n; i++) {
      cerr << secondBestPath[i] << " ";
    }
    cerr << endl;

    for (int i = 0; i < n; i++) {
      cerr << downAnswer[i] << " ";
    }
    cerr << endl;

    for (int i = 0; i < n; i++) {
      cerr << upAnswer[i] << " ";
    }
    cerr << endl;
  }
}

int distance(int x, int y) {
  int z = lca(x, y);
  return L[x] + L[y] - 2 * L[z];
}

int getUpVertex(int x, int d) {
  for (int i = LN - 1; i >= 0; i--) {
    if (d >= (1 << i)) {
      x = DP[x][i];
      d -= (1 << i);
    }
  }
  return x;
}

pair<int, int> handleTom(int x, int y) {
  int d = distance(x, y);
  int jerry_position;
  int up = getUpVertex(x, d / 2);
  int tom_position = up;
  int curDistance = distance(up, y);

  if (tom_position != lca(x, y)) {
    jerry_position = parent[tom_position];
  } else {
    jerry_position = getUpVertex(y, distance(lca(x, y), y) - 1);
  }

  /*
  int brute_jerry_position = 0;
  //cerr << "total size " << g[up].size() << endl;
  for (int to: g[up]) {
    if (distance(to, y) < curDistance) {
      brute_jerry_position = to;
    }
  }

  if (jerry_position != brute_jerry_position) {
    fprintf(stderr, "jerry_position = %d, brute_jerry_position = %d\n", jerry_position, brute_jerry_position);
  }

  assert(jerry_position == brute_jerry_position);
  */

  return make_pair(tom_position, jerry_position);
}

pair<int, int> handleJerry(int x, int y) {
  int d = distance(x, y);
  int up = getUpVertex(y, (d - 1) / 2);
  //fprintf(stderr, "d=%d, up=%d\n", d, up);
  return make_pair(parent[up], up);
}

int findAns(int x, int y) {
  if (x == y) {
    return 0;
  }

  int z = lca(x, y);
  int d = distance(x, y);
  pair<int, int> positions;
  if (z == x || z == y) {
    if (L[x] > L[y]) {
      positions = handleTom(x, y);
    } else {
      positions = handleJerry(x, y);
    }
  } else {
    if (distance(x, z) >= distance(y, z)) {
      positions = handleTom(x, y);
    } else {
      positions = handleJerry(x, y);
    }
  }
  int tom_position = positions.first;
  int jerry_position = positions.second;
  int ans = distance(x, tom_position);
  
  int added = 1;
  //dp(tom_position, jerry_position);
  
  if (tom_position == parent[jerry_position]) {
    added += downAnswer[jerry_position];
  } else {
    added += upAnswer[tom_position];
  }
  
  /*
  int badded = dp(tom_position, jerry_position);

  cerr << "added " << added << endl;
  cerr << "badded " << badded << endl;

  if (DEBUG) {
    fprintf(stderr, "tom_position = %d, jerry_position = %d, ans = %d\n", tom_position, jerry_position, ans);
    fprintf(stderr, "dp val = %d\n", dp(tom_position, jerry_position));
  }

  assert(added == badded);
  */

  ans += added;

  if (DEBUG) {
    fprintf(stderr, "tom_position = %d, jerry_position = %d, ans = %d\n", tom_position + 1, jerry_position + 1, ans);
    //fprintf(stderr, "dp val = %d\n", dp(tom_position, jerry_position));
  }
  return ans;
}


void increaseStackSize() {
  const rlim_t kStackSize = 64 * 1024 * 1024;   // min stack size = 16 MB
  struct rlimit rl;
  int result;

  result = getrlimit(RLIMIT_STACK, &rl);
  cerr << "result " << result << endl;
  if (result == 0)
  {
      cerr << rl.rlim_cur << endl;
      if (rl.rlim_cur < kStackSize)
      {
          rl.rlim_cur = kStackSize;
          result = setrlimit(RLIMIT_STACK, &rl);
            cerr << "result " << result << endl;

          if (result != 0)
          {
              fprintf(stderr, "setrlimit returned result = %d\n", result);
          }
      }
  }
}

int main() {
  increaseStackSize();
  //freopen("8.in", "r", stdin);

  int T;
  scanf("%d", &T);
  assert(T >= 1 && T <= 10);

  int cnt = 0;
  int test = 1;
  while (T--) {
    cerr << "processing test = " << test++ << endl;

    scanf("%d %d", &n, &Q);
    cerr << "n " << n << " Q " << Q << endl;

    assert(n >= 1 && n <= MAXN);
    assert(Q >= 1 && Q <= MAXN);

    for(int i = 0; i < n ; i++){
      DP[i][0] = -1;
    }

    set<pair<int, int> > st;
    REP(i, n - 1) {
      int u, v;
      scanf("%d %d", &u, &v);
      u--; v--;
      //cerr << "i " << i << " u " << u << " v " << v << endl;
      assert(u >= 0 && u < n);
      assert(v >= 0 && v < n);
      assert(u != v);
      g[u].push_back(v);
      g[v].push_back(u);
      if (u > v) swap(u, v);
      st.insert(make_pair(u, v));
    }
    assert(st.size() == n - 1);
    
    setup();

    cerr << "setup done" << endl;

    while (Q--) {
      int u, v;
      scanf("%d %d", &u, &v);
      u--; v--;
      printf("%d\n", findAns(u, v));
    }

    for(int i = 0; i < n ; i++){
      g[i].clear();
      DP[i][0] = -1;
    }
  }
  
  return 0;
}