fn main() {
let _io = io();
for _ in 0..r!(U) {
let n = r!(U);
let mut edges = vec![vec![]; n];
for _ in 1..n {
let (u, v) = r!(usize, usize);
edges[u - 1].push(v - 1);
edges[v - 1].push(u - 1);
}
for u in 0..n {
edges[u].sort_unstable();
}
fn dfs1(u: U, p: U, edges: &mut Vec<Vec<U>>, leafs: &mut Vec<U>) -> U {
if edges[u].len() == 1 && edges[u][0] == p {
return U::MAX;
}
let mut mn = U::MAX;
let mut tbr = vec![];
for &v in &edges[u].clone() {
if v != p {
let x = dfs1(v, u, edges, leafs);
if x == U::MAX {
tbr.push(v)
}
mn = mn.min(x);
}
}
leafs[u] = tbr.len();
tbr.push(U::MAX);
let mut new = vec![];
let mut i = 0;
let mut j = 0;
while i < edges[u].len() {
if edges[u][i] == tbr[j] {
i += 1;
j += 1;
} else if edges[u][i] < tbr[j] {
new.push(edges[u][i]);
i += 1;
} else {
j += 1;
}
}
edges[u] = new;
mn.min(edges[u].len() + leafs[u])
}
let mut leafs = vec![0; n];
let mx = dfs1(0, 0, &mut edges, &mut leafs);
fn dfs2(u: U, p: U, edges: &Vec<Vec<U>>, leafs: &Vec<U>, k: U) -> (N, N) {
// (s == k, s == k - 1)
let mut polys = vec![vec![N::ONE]];
for &v in &edges[u] {
if v != p {
let (a, b) = dfs2(v, u, edges, leafs, k);
polys.push(vec![a, b]);
}
}
fn work(mut polys: Vec<Vec<N>>, k: U) -> Vec<N> {
if polys.is_empty() {
vec![]
} else if polys.len() == 1 {
polys.remove(0)
} else {
let m = polys.len() >> 1;
let new = polys.split_off(m);
let r1 = work(polys, k);
let r2 = work(new, k);
let mut res = multiply(r1, r2);
res.truncate(k + 2);
res
}
}
let mut n1 = N::ZERO;
let mut n0 = N::ZERO;
let leafs = leafs[u];
for (i, r) in work(polys, k).into_iter().enumerate() {
for (j, nn) in [(k, &mut n0), (k - 1, &mut n1)] {
if i > j {
continue;
}
let d = j - i;
*nn += r * leafs.choose(d);
}
}
(n0, n1)
}
let mut ans = N::ONE;
for k in 1..=mx {
ans += dfs2(0, 0, &edges, &leafs, k).0;
}
w!(ans);
}
}
static mut SEEN: Vec<(N, N)> = Vec::new();
#[allow(static_mut_refs)]
fn get_seen() -> &'static mut Vec<(N, N)> {
unsafe { &mut SEEN }
}
/// use `init_seen` to get initial "dp" memoization table, doubles size on miss (why not)
pub trait Combinatorics {
fn choose(self, k: usize) -> N;
fn fact(self) -> N;
fn inv_fact(self) -> N;
}
impl Combinatorics for usize {
fn choose(self, k: usize) -> N {
if self < k {
N::ZERO
} else {
self.fact() * (self - k).inv_fact() * k.inv_fact()
}
}
fn fact(self) -> N {
let seen = get_seen();
while self >= seen.len() {
init_seen(seen);
}
seen[self].0
}
fn inv_fact(self) -> N {
let seen = get_seen();
while self >= seen.len() {
init_seen(seen);
}
seen[self].1
}
}
fn init_seen(seen: &mut Vec<(N, N)>) {
if seen.is_empty() {
seen.push((N::ONE, N::ONE));
}
let mut cur = seen.l().0;
let mut cur_inv = seen.l().1;
for i in seen.len()..seen.len() * 2 {
cur *= N::new(i);
cur_inv /= N::new(i);
seen.push((cur, cur_inv));
}
}
// require mod_int
// to find primitive roots: https://www.wolframalpha.com/input/?i=PrimitiveRoots%5B%5B%2F%2Fnumber%3A998244353%2F%2F%5D%5D
const C: usize = 119;
const ROOT_PW: usize = 1 << 23;
const G: M = M::new(3);
const ROOT: M = G.pow(C);
const ROOT_1: M = ROOT.inv();
type M = Mod;
// from https://cp-algorithms.com/algebra/fft.html#number-theoretic-transform
pub fn fft(a: &mut Vec<M>, invert: bool) {
let n = a.len();
let mut j = 0;
for i in 1..n {
let mut bit = n >> 1;
while j & bit != 0 {
j ^= bit;
bit >>= 1;
}
j ^= bit;
if i < j {
a.swap(i, j);
}
}
let mut len = 2;
while len <= n {
let mut wlen = if invert { ROOT_1 } else { ROOT };
let mut i = len;
while i < ROOT_PW {
wlen *= wlen;
i <<= 1;
}
for i in (0..n).step_by(len) {
let mut w = M::ONE;
for j in 0..len / 2 {
let u = a[i + j];
let v = a[i + j + len / 2] * w;
a[i + j] = u + v;
a[i + j + len / 2] = u - v;
w *= wlen;
}
}
len <<= 1;
}
if invert {
let n_1 = M::new(n).inv();
for x in a {
*x *= n_1;
}
}
}
pub fn multiply(mut fa: Vec<M>, mut fb: Vec<M>) -> Vec<M> {
let n = (fa.len() + fb.len()).next_power_of_two();
fa.resize(n, M::ZERO);
fb.resize(n, M::ZERO);
fft(&mut fa, false);
fft(&mut fb, false);
for (fai, fbi) in fa.iter_mut().zip(fb) {
*fai *= fbi;
}
fft(&mut fa, true);
fa
}
const MOD: usize = 998_244_353;
// const MOD: usize = 1_000_000_007;
type N = Mod;
use std::ops::*;
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Default, Debug)]
pub struct Mod(pub usize);
#[allow(unused)]
impl Mod {
const ZERO: Self = Self::new(0);
const NEG_ONE: Self = Self::newi(-1);
const ONE: Self = Self::new(1);
const TWO: Self = Self::new(2);
const NEG_TWO: Self = Self::newi(-2);
const INV_TWO: Self = Self::new(2).inv();
pub const fn newi(x: isize) -> Self {
Self::new(((x % MOD as isize) + MOD as isize) as usize)
}
fn new2(x: usize) -> Self {
debug_assert!(x < MOD << 1);
if x >= MOD { Self(x - MOD) } else { Self(x) }
}
pub const fn new(x: usize) -> Self {
Self(x % MOD)
}
pub const fn pow(self, mut e: usize) -> Self {
let mut res = Self(1);
let mut cur = self;
while e > 0 {
if e & 1 == 1 {
res = res.fast_mul(cur);
}
cur = cur.fast_mul(cur);
e >>= 1;
}
res
}
pub const fn inv(self) -> Self {
#[cfg(debug_assertions)]
if self.0 == 0 {
panic!("Division by `0`.");
}
self.pow(MOD - 2)
}
pub const fn fast_mul(self, rhs: Self) -> Self {
if MOD < u32::MAX as usize {
Self((self.0 * rhs.0) % MOD)
} else {
Self(((self.0 as u128 * rhs.0 as u128) % MOD as u128) as usize)
}
}
}
impl std::iter::Sum for Mod {
fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
iter.fold(Self::ZERO, |a, b| a + b)
}
}
impl std::iter::Product for Mod {
fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
iter.fold(Self::ONE, |a, b| a * b)
}
}
impl std::fmt::Display for Mod {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.pad_integral(true, "", &self.0.to_string())
}
}
impl AsRef<usize> for Mod {
fn as_ref(&self) -> &usize {
&self.0
}
}
impl AsMut<usize> for Mod {
fn as_mut(&mut self) -> &mut usize {
&mut self.0
}
}
impl Add for Mod {
type Output = Self;
fn add(self, rhs: Self) -> Self {
Self::new2(self.0 + rhs.0)
}
}
impl Add<usize> for Mod {
type Output = Self;
fn add(self, rhs: usize) -> Self {
self + Self::new(rhs)
}
}
impl Sub for Mod {
type Output = Self;
fn sub(self, rhs: Self) -> Self {
Self::new2(self.0 + MOD - rhs.0)
}
}
impl Sub<usize> for Mod {
type Output = Self;
fn sub(self, rhs: usize) -> Self {
self - Self::new(rhs)
}
}
impl Mul for Mod {
type Output = Self;
fn mul(self, rhs: Self) -> Self {
self.fast_mul(rhs)
}
}
impl Mul<usize> for Mod {
type Output = Self;
fn mul(self, rhs: usize) -> Self {
if MOD < u32::MAX as usize {
Self((self.0 * rhs) % MOD)
} else {
Self(((self.0 as u128 * rhs as u128) % MOD as u128) as usize)
}
}
}
impl Div for Mod {
type Output = Self;
fn div(self, rhs: Self) -> Self {
self * rhs.inv()
}
}
impl Div<usize> for Mod {
type Output = Self;
fn div(self, rhs: usize) -> Self {
self * Mod::new(rhs).inv()
}
}
impl Neg for Mod {
type Output = Self;
fn neg(self) -> Self::Output {
if self.0 == 0 {
self
} else {
Self(MOD - self.0)
}
}
}
impl Neg for &Mod {
type Output = Mod;
fn neg(self) -> Self::Output {
-*self
}
}
macro_rules! impl_mod_rest {
($($trait:ident::$fn:ident:$trait_assign:ident::$fn_assign:ident;)*) => {
$(
impl $trait<&Mod> for Mod {
type Output = Mod;
fn $fn(self, rhs: &Mod) -> Self::Output {
$trait::$fn(self, *rhs)
}
}
impl $trait<&Mod> for &Mod {
type Output = Mod;
fn $fn(self, rhs: &Mod) -> Self::Output {
$trait::$fn(*self, *rhs)
}
}
impl $trait<Mod> for &Mod {
type Output = Mod;
fn $fn(self, rhs: Mod) -> Self::Output {
$trait::$fn(*self, rhs)
}
}
impl $trait<&usize> for Mod {
type Output = Mod;
fn $fn(self, rhs: &usize) -> Self::Output {
$trait::$fn(self, *rhs)
}
}
impl $trait<&usize> for &Mod {
type Output = Mod;
fn $fn(self, rhs: &usize) -> Self::Output {
$trait::$fn(*self, *rhs)
}
}
impl $trait<usize> for &Mod {
type Output = Mod;
fn $fn(self, rhs: usize) -> Self::Output {
$trait::$fn(*self, rhs)
}
}
impl $trait_assign for Mod {
fn $fn_assign(&mut self, rhs: Mod) {
*self = $trait::$fn(*self, rhs);
}
}
impl $trait_assign<&Mod> for Mod {
fn $fn_assign(&mut self, rhs: &Mod) {
*self = $trait::$fn(*self, rhs);
}
}
impl $trait_assign<usize> for Mod {
fn $fn_assign(&mut self, rhs: usize) {
*self = $trait::$fn(*self, rhs);
}
}
impl $trait_assign<&usize> for Mod {
fn $fn_assign(&mut self, rhs: &usize) {
*self = $trait::$fn(*self, rhs);
}
}
)*
};
}
impl_mod_rest! {
Add::add:AddAssign::add_assign;
Sub::sub:SubAssign::sub_assign;
Mul::mul:MulAssign::mul_assign;
Div::div:DivAssign::div_assign;
}
pub fn lcm(u: U, v: U) -> U {
u * v / gcd(u, v)
}
// gcd from wiki: https://en.wikipedia.org/wiki/Binary_GCD_algorithm
pub fn gcd(mut u: U, mut v: U) -> U {
if u == 0 {
return v;
} else if v == 0 {
return u;
}
let i = u.trailing_zeros();
u >>= i;
let j = v.trailing_zeros();
v >>= j;
let k = std::cmp::min(i, j);
loop {
if u > v {
std::mem::swap(&mut u, &mut v);
}
v -= u;
if v == 0 {
return u << k;
}
v >>= v.trailing_zeros();
}
}
/// Slower but more robust RNG
pub mod rng2 {
pub struct Rng {
seed: u64,
}
impl Rng {
pub fn new() -> Self {
Self {
seed: std::time::SystemTime::now()
.duration_since(std::time::SystemTime::UNIX_EPOCH)
.unwrap()
.as_nanos() as u64,
}
}
pub fn next(&mut self) -> u64 {
use std::num::Wrapping;
let mut x = Wrapping(self.seed);
x += Wrapping(0x9e3779b97f4a7c15);
x = (x ^ (x >> 30)) * Wrapping(0xbf58476d1ce4e5b9);
x = (x ^ (x >> 27)) * Wrapping(0x94d049bb133111eb);
x ^= x >> 31;
self.seed = x.0;
return self.seed;
}
pub fn next_u64(&mut self) -> u64 {
self.next()
}
pub fn next_u128(&mut self) -> u128 {
let (l, u) = (self.next_u64(), self.next_u64());
((l as u128) << 64) | u as u128
}
pub fn next_u(&mut self) -> usize {
self.next_u64() as usize
}
}
}
pub struct Rng {
seed: u32,
}
impl Rng {
pub fn new() -> Self {
Self {
seed: std::time::SystemTime::now()
.duration_since(std::time::SystemTime::UNIX_EPOCH)
.unwrap()
.subsec_nanos(),
}
}
pub fn next(&mut self) -> u32 {
self.seed ^= self.seed << 13;
self.seed ^= self.seed >> 17;
self.seed ^= self.seed << 5;
self.seed
}
pub fn next_u64(&mut self) -> u64 {
let (l, u) = (self.next(), self.next());
((l as u64) << 32) | u as u64
}
pub fn next_u128(&mut self) -> u128 {
let (l, u) = (self.next_u64(), self.next_u64());
((l as u128) << 64) | u as u128
}
pub fn next_u(&mut self) -> usize {
self.next_u64() as usize
}
}
pub trait IterExt<T> {
fn n(&mut self) -> T;
fn cv(self) -> Vec<T>;
}
impl<T, I: Iterator<Item = T>> IterExt<T> for I {
fn cv(self) -> Vec<T> {
self.collect()
}
fn n(&mut self) -> T {
self.next().unwrap()
}
}
pub trait IterExt2<T: PartialOrd> {
fn mn(self) -> T;
fn mx(self) -> T;
}
impl<T: PartialOrd, I: IntoIterator<Item = T>> IterExt2<T> for I {
fn mn(self) -> T {
self.into_iter()
.min_by(|a, b| a.partial_cmp(b).unwrap())
.unwrap()
}
fn mx(self) -> T {
self.into_iter()
.max_by(|a, b| a.partial_cmp(b).unwrap())
.unwrap()
}
}
pub trait IterExt3<T: ToString> {
fn to_string(self, sep: &str) -> String;
}
impl<T: ToString, I: IntoIterator<Item = T>> IterExt3<T> for I {
fn to_string(self, sep: &str) -> String {
self.into_iter().map(|x| x.to_string()).cv().join(sep)
}
}
pub trait IterExt4<T: Clone> {
fn l(&self) -> T;
}
impl<T: Clone> IterExt4<T> for Vec<T> {
fn l(&self) -> T {
self[self.len() - 1].clone()
}
}
impl<T: Clone> IterExt4<T> for &[T] {
fn l(&self) -> T {
self[self.len() - 1].clone()
}
}
impl<T: Clone> IterExt4<T> for &mut [T] {
fn l(&self) -> T {
self[self.len() - 1].clone()
}
}
pub use lib::*;
#[allow(unused)]
mod lib {
pub type U = usize;
pub type I = isize;
pub type F = f64;
pub use std::cmp::{Ordering, Reverse};
pub use std::collections::*;
pub use std::f64::consts::*;
pub use std::fmt::Write;
use std::io::*;
use std::iter::Filter;
use std::str::{Split, SplitWhitespace};
pub struct Output(String);
impl AsRef<String> for Output {
fn as_ref(&self) -> &String {
&self.0
}
}
impl AsMut<String> for Output {
fn as_mut(&mut self) -> &mut String {
&mut self.0
}
}
static mut OUTPUT: Output = Output(String::new());
#[inline(always)]
#[allow(static_mut_refs)]
pub fn output() -> &'static mut Output {
unsafe { &mut OUTPUT }
}
#[macro_export]
macro_rules! w {
() => {{
let _ = writeln!(output().as_mut());
}};
($t:expr) => {{
let _ = writeln!(output().as_mut(), "{}", $t);
}};
($$$start:expr $$$(,$$$t:expr)* $$$(,)?) => {{
let o = output().as_mut();
let _ = write!(o, "{}", $start);
$(
let _ = write!(o, " {}", $t);
)*
let _ = writeln!(o);
}};
}
type InputInner = (Split<'static, &'static [char]>, String);
pub struct Input(InputInner); // must drop both at the same time (or the iterator first)
impl Input {
#[inline(always)]
pub fn get_next(&mut self) -> &'static str {
loop {
if let Some(n) = self.0.0.next() {
if !n.is_empty() {
return n;
}
} else {
self.0 = read_next_line();
}
}
}
}
const SKIP_CHARS: [char; 5] = [' ', '\n', '\r', '\t', ','];
fn read_next_line() -> InputInner {
let mut s = String::new();
stdin().read_line(&mut s).unwrap();
let ss: &'static mut str = unsafe { std::mem::transmute(s.as_mut_str()) };
(ss.split(&SKIP_CHARS), s)
}
static mut INPUT: Option<Input> = None;
#[inline(always)]
#[allow(static_mut_refs)]
pub fn input() -> &'static mut Input {
unsafe { INPUT.as_mut().unwrap_unchecked() }
}
pub trait Parse {
type ParsesTo;
#[inline(always)]
fn parse(i: &mut Input) -> Self::ParsesTo;
}
pub struct IO;
impl Drop for IO {
fn drop(&mut self) {
print!("{}", output().0);
}
}
macro_rules! impl_parse {
($($t:tt),*) => {
$(
impl Parse for $t {
type ParsesTo = Self;
#[inline(always)]
fn parse(i: &mut Input) -> Self::ParsesTo {
<Self as std::str::FromStr>::from_str(&i.get_next()).unwrap()
}
}
)*
};
}
impl_parse!(
bool, u8, i8, char, u16, i16, u32, i32, f32, u64, i64, f64, usize, isize, u128, i128
);
impl Parse for String {
type ParsesTo = Vec<char>;
fn parse(i: &mut Input) -> Self::ParsesTo {
i.get_next().chars().collect()
}
}
impl<T: Parse<ParsesTo = U>, U> Parse for Vec<T> {
type ParsesTo = Vec<U>;
fn parse(i: &mut Input) -> Self::ParsesTo {
let n = usize::parse(i);
(0..n).map(|_| T::parse(i)).collect()
}
}
#[inline(always)]
pub fn lin<T: Parse<ParsesTo = U>, U, V: FromIterator<U>>(n: usize) -> V {
let i = input();
(0..n).map(|_| T::parse(i)).collect()
}
#[inline(always)]
pub fn grid<T: Parse<ParsesTo = U>, U, V: FromIterator<U>, W: FromIterator<V>>(
n: usize,
m: usize,
) -> W {
(0..n).map(|_| lin::<T, U, V>(m)).collect()
}
#[macro_export]
macro_rules! rv {
($n:expr; $c:tt<$t:tt>) => {
lin::<$t, _, $c<_>>($n)
};
($n:expr, $m:expr; $c1:tt<$c2:tt<$t:tt>>) => {
grid::<$t, _, $c2<_>, $c1<$c2<_>>>($n, $m)
};
}
#[macro_export]
macro_rules! r {
(<p>Unable to parse markup [type=CF_MATHJAX]</p>(,)?) => {{
let i = input();
($(<$t as Parse>::parse(i)),*)
}};
}
pub fn io() -> IO {
let (mut i, mut o) = (Some(Input(read_next_line())), Output(String::new()));
unsafe {
INPUT = i;
OUTPUT = o; // fairly useless, can be removed; currently only "resets" output string
// (which should be a noop)
}
IO
}
}
)
