Problem Description

小$x$正在勤奋地做题，一天他看到了一个问题：

给定一棵树，你需要给每条边定向，使其变成一张n个节点，n-1条有向边的有向图，你需要给出一个合理的定向方案使得这张图中的简单路径数量最大。

对于一条简单路径(u,v)，需要满足存在一条路径序列u,k1,k2...kx,v满足存在u->k1,k1->k2....kx->v的有向边。

小$x$很快地解决了这道题目，但他并不喜欢总是在题目里输出方案，于是他对题目进行了一些改动：

对于一棵以1号节点为根节点的有根树，对于其每一棵子树，求出对子树内部的边进行定向后的最大简单路径数。

注意：对于每棵子树来讲，问题都是独立的，也就是说，对于每一条边，它在不同的子树中的定向方案可能是不同的。

Input

第一行输入一行一个正整数$T[1\leq T\leq 3]$代表数据组数。

对于每组测试数据，第一行输入一行一个正整数$n [1\leq n\leq 100000 ]$,代表树的节点数。

第2行到第$n$行，每行两个正整数$u,v [1\leq u,v\leq n ]$，代表树上的一条边。

Output

对于每组数据，输出$n$行$n$个正整数，第$i$行代表以$i$号节点为根的子树的答案。

1
5
1 2
2 3
3 4
3 5

14
9
6
1
1