Assume that you have k one-dimensional segments s_1, s_2, ... s_k (each segment is denoted by two integers — its endpoints). Then you can build the following graph on these segments. The graph consists of k vertexes, and there is an edge between the i-th and the j-th vertexes (i ≠ j) if and only if the segments s_i and s_j intersect (there exists at least one point that belongs to both of them).

For example, if s_1 = [1, 6], s_2 = [8, 20], s_3 = [4, 10], s_4 = [2, 13], s_5 = [17, 18], then the resulting graph is the following:

<image>

A tree of size m is good if it is possible to choose m one-dimensional segments so that the graph built on these segments coincides with this tree.

You are given a tree, you have to find its good subtree with maximum possible size. Recall that a subtree is a connected subgraph of a tree.

Note that you have to answer q independent queries.

Input

The first line contains one integer q (1 ≤ q ≤ 15 ⋅ 10^4) — the number of the queries. 

The first line of each query contains one integer n (2 ≤ n ≤ 3 ⋅ 10^5) — the number of vertices in the tree.

Each of the next n - 1 lines contains two integers x and y (1 ≤ x, y ≤ n) denoting an edge between vertices x and y. It is guaranteed that the given graph is a tree.

It is guaranteed that the sum of all n does not exceed 3 ⋅ 10^5.

Output

For each query print one integer — the maximum size of a good subtree of the given tree.

Example

Input


1
10
1 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
4 10


Output


8

Note

In the first query there is a good subtree of size 8. The vertices belonging to this subtree are {9, 4, 10, 2, 5, 1, 6, 3}.
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 3e5 + 15;
int q, n, ans;
bool mark[MAX_N];
int d[MAX_N];
vector<int> G[MAX_N];
int dfs(int v, int p = -1) {
  int res1 = 0, res2 = 0, ct = 0;
  for (int u : G[v])
    if (u != p && !mark[u]) {
      ct++;
      int tmp = dfs(u, v);
      if (res1 < tmp) {
        res2 = res1;
        res1 = tmp;
      } else
        res2 = max(res2, tmp);
    }
  ans = max(ans, d[v] + res1 + res2 + ct - 2 + (p != -1));
  ans = max(ans, d[v] + res1 + max(0, ct - 1 + (p != -1)));
  ans = max(ans, d[v] + ct + (p != -1));
  return d[v] + max(res1 + max(0, ct - 1), ct);
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  fill(d, d + MAX_N, 1);
  cin >> q;
  while (q--) {
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
      int v, u;
      cin >> v >> u;
      v--, u--;
      G[v].push_back(u);
      G[u].push_back(v);
    }
    if (n == 2) {
      cout << 2 << "\n";
      for (int i = 0; i < n; i++) G[i].clear();
      continue;
    }
    for (int i = 0; i < n; i++)
      if (G[i].size() == 1) {
        mark[i] = true;
        d[G[i][0]]++;
      }
    int V = 0;
    for (int i = 0; i < n; i++)
      if (!mark[i]) V = i;
    dfs(V);
    cout << ans << "\n";
    fill(mark, mark + n, 0);
    fill(d, d + n, 1);
    ans = 0;
    for (int i = 0; i < n; i++) G[i].clear();
  }
  return 0;
}
