There are \(n\) cities in the country with \(n-1\) roads connecting them. In other words, the country can be represented as a tree. Pisces is now in city \(1\), and he wants to know the distance from his current position to each of the other cities. Here the distance between cities \(A\) and \(B\) is defined as the number of roads in the simple path (a path without duplicate cities) from \(A\) to \(B\).

The first line contains an interger \(T(1\leq T\leq 10)\), which represents the number of test cases.

For each of the test case, the first line contains an integer \(n(1\leq n\leq 10^4)\), which is the number of cities. Each of the next \(n-1\) lines contains \(2\) interger \(u\) and \(v(1\leq u, v\leq n)\), representing that there is a road from city \(u\) to city \(v\).

For each test case, print \(n\) integers. The \(i\)-th interger represents the distance from city \(1\) to city \(i\). Especially, the distance of city \(1\) itself is \(0\).