주어진 트리 $T$에 대해, 모든 부분 트리 $T'$에 대한 $f(T')$의 합을 998244353으로 나눈 나머지를 계산하세요. 두 부분 트리는 꼭짓점 집합이나 간선 집합이 다르면 서로 다른 것으로 간주됩니다.

이 문제에서는 부분 트리와 지름에 대한 특이한 정의를 사용합니다.

다음은 몇 가지 정의입니다:

• 트리 $T$의 크기는 $T$에 포함된 꼭짓점의 수, 즉 $|V(T)|$입니다.
• 트리 $T$에서 꼭짓점 $i$의 차수는 해당 꼭짓점에 연결된 간선의 수이며, $deg_i$로 표시됩니다.
• 트리 $T'$가 트리 $T$의 부분 트리라는 것은 다음을 의미합니다:
  • $V(T')$의 모든 꼭짓점 $v$에 대해 $v \in V(T)$입니다.
  • $E(T')$의 모든 간선 $e$에 대해 $e \in E(T)$입니다.
• $S_T$를 $T$의 모든 부분 트리의 집합이라고 합시다.
• 트리 $T$의 지름은 부분 트리 $T'$ 중에서 $max(deg_i) \le 2$를 만족하는 가장 큰 크기의 부분 트리 $T'$의 크기입니다.
• $R_x$를 $max(deg_i) \le 3$을 만족하는 가장 큰 트리들의 집합이라고 합시다.
• 트리의 지름은 $2x$입니다.
• 트리 $T$에 대해, $S_T \cap R_k \neq \emptyset$을 만족하는 가장 큰 $k$를 $f(T)$라고 합시다. 그러한 $k$가 없다면 $f(T) = 0$입니다.

입력

각 테스트 케이스는 여러 개의 테스트 케이스를 포함합니다. 첫 번째 줄에는 테스트 케이스의 수를 나타내는 정수 $t$ ($1 \le t \le 5 \times 10^4$)가 주어집니다. 테스트 케이스 설명이 이어집니다.

첫 번째 줄에는 트리의 꼭짓점 수를 나타내는 정수 $n$ ($1 \le n \le 10^5$, $\sum n \le 10^6$)이 주어집니다. 이어지는 $n-1$개의 줄에는 두 정수 $u, v$ ($1 \le u \neq v \le n$)가 주어지며, 이는 트리 $T$의 간선을 나타냅니다.

출력

각 테스트 케이스에 대해, $f(T')$의 합을 998244353으로 나눈 나머지를 한 줄에 하나씩 출력합니다.

예제

입력 1

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

출력 1

12
94

참고 1

첫 번째 테스트 케이스의 경우, 17개의 서로 다른 부분 트리가 있습니다. 5개의 부분 트리는 꼭짓점이 하나만 포함되어 $f(T') = 0$입니다. 나머지 모든 부분 트리는 $f(T') = 1$을 만족합니다. 따라서 답은 12입니다.