Every week you take a socially-distanced trip to Overwaitea, your favourite grocery store, to stock up on food. Out front, there are \(N\) shopping carts, numbered from \(1\) to \(N\). To dissuade theft, the carts are locked together and you need to insert a quarter to unlock one cart from the rest. When you return your cart, you get your quarter back. Now that you think about it, maybe 25 Canadian cents is actually a pretty good deal for your very own shopping cart...

Each cart has a connecting chain leading out of it. There are also \(N+2\) latches, numbered from \(1\) to \(N+2\), which chains may be connected to (with each latch having at most one incoming chain). Each of the first \(N\) latches can be found on carts, with latch \(i\) fixed to cart \(i\). The remaining two latches (latches \(N+1\) and \(N+2\)) are instead mounted to a wall. Each cart \(i\)'s chain is initially connected to latch \(A_i\), but you suspect it would be more aesthetically pleasing if it was instead attached to an ideal target latch \(B_i\).

A *sequence* of \(K\) carts \(S_{1..K}\) is one in which latch \(S_1\) has no incoming chain, cart \(S_1\)'s chain connects to latch \(S_2\), cart \(S_2\)'s chain connects to latch \(S_3\), and so on, with cart \(S_{K-1}\)'s chain connecting to latch \(S_K\), and cart \(S_K\)'s chain not connecting to any cart (but rather to either a wall latch or no latch).

The carts are rigid enough that it's impossible to ever form a "cycle" of carts, such that repeatedly following chain connections forwards from an initial cart will result in returning to that initial cart. This means that each cart is always part of exactly one *sequence*, and is present in that *sequence* exactly once.

The values of \(A_{1..N}\) and \(B_{1..N}\) are given such that the carts initially form a valid configuration (with no "cycles"), and would also form a valid configuration if every cart's chain were to be connected to its ideal target latch.

For example, if \(N = 3\) and \(A = [4, 1, 5]\), the initial configuration looks as follows (having two *sequences* of carts \([2, 1]\) and \([3]\)):

{{PHOTO_ID:1217734278611436}}

You may repeatedly perform either of the following actions before leaving the carts in a desired *final state*, in which every chain must end up once again connected to a latch:

1. Pay 1 quarter (if you have at least 1) to detach any given cart's chain from whichever latch it's currently connected to (if any)
2. Gain 1 quarter by attaching any given cart's currently-unattached chain to a latch (as long as no other chain is currently connected to that latch, and a "cycle" of carts would not be formed)

For example, beginning with the above configuration and with at least 1 quarter in hand, you could perform **action 1** to detach cart 1's chain and produce the following configuration (which is *not* a valid *final state* due to cart 1's chain not being connected to any latch):

{{PHOTO_ID:3302289739857297}}

You could then perform **action 2** to attach cart 1's chain to cart 3's latch (forming a valid *final state*):

{{PHOTO_ID:766911834140516}}

Consider a hypothetical scenario in which:

- You begin with \(Q\) quarters
- A *sequence* consisting of more than \(C\) carts must never be present (including initially)
- The *final state* must not have a *sequence* consisting of more than \(X\) carts attached to latch \(N+1\)
- The *final state* must not have a *sequence* consisting of more than \(Y\) carts attached to latch \(N+2\)

Let \(F(Q, C, X, Y)\) be the maximum number of chains which can end up connected to their ideal target latches in a *final state* given such a scenario, or \(-1\) if it's impossible to achieve a valid *final state* at all.

Let \(G(v)\) be the number of quadruples \((Q, C, X, Y)\) such that \(0 \le Q, C, X, Y \le N\) and \(F(Q, C, X, Y) = v\). You'd like to compute \(G(v)\) for each integer \(v\) such that \(-1 \le v \le N\).

# Constraints

\(1 \le T \le 85\)
\(1 \le N \le 700\)
\(1 \le A_i, B_i \le N+2\)

The sum of \(N\) across all test cases is at most 7000.

# Input

Input begins with an integer \(T\), the number of sets of shopping carts. For each set there are \(N+1\) lines. The first contains the integer \(N\). \(N\) lines follow, the \(i\)th of which contains the space-separated integers \(A_i\) and \(B_i\).

# Output

For each set of shopping carts, print a line containing *"Case #i: "*, followed by \(N+2\) integers, \(G(-1)\), \(G(0)\), \(G(1)\), ..., \(G(N-1)\), \(G(N)\), as defined above.

# Explanation of Sample

In the first case, the initial configuration is as follows:

{{PHOTO_ID:3371452566235882}}

There are \(2^4 = 16\) quadruples \((Q, C, X, Y)\) to consider. For 11 of them, \(F(Q, C, X, Y) = -1\), while the following 5 yield different results:

- \(F(0, 1, 1, 0) = 0\)
- \(F(0, 1, 1, 1) = 0\)
- \(F(1, 1, 1, 0) = 0\)
- \(F(1, 1, 0, 1) = 1\)
- \(F(1, 1, 1, 1) = 1\)

Several evaluations of \(F(Q, C, X, Y)\) are explained below:

- \(F(1, 0, 1, 1) = -1\) because the initial configuration features a *sequence* of 1 cart, which is disallowed due to \(C = 0\).
- \(F(1, 1, 0, 0) = -1\) because every possible *final state* features a *sequence* of 1 cart connected to either latch 2 or latch 3, which is disallowed due to \(X = Y = 0\).
- \(F(0, 1, 1, 1) = 0\) because no action may initially taken without at least 1 quarter.
- \(F(1, 1, 0, 1) = 1\) because you may spend your 1 quarter to disconnect cart 1's chain from latch 2, and then gain your quarter back while connecting it to latch 3 (its ideal target latch).

In the second case, the initial configuration is as follows:

{{PHOTO_ID:1217734278611436}}

Several evaluations of \(F(Q, C, X, Y)\) are explained below:

- \(F(3, 2, 2, 2) = 3\) because you may spend your 3 quarters disconnecting all of the carts' chains, and then gain your quarters back while connecting the carts' chains to their ideal target latches in any order (without a *sequence* of more than 2 carts ever being present). This yields the following *final state*:

{{PHOTO_ID:2978496958918891}}

- \(F(3, 3, 3, 1) = 2\) because you may similarly disconnect and then reconnect all of the carts' chains, but cannot arrive at the same *final state* as above (as it features a *sequence* of 2 carts connected to latch 5, which is disallowed due to \(Y = 1\)). This means that only up to 2 chains may end up connected to their ideal target latches instead, for example as in the following *final state*:

{{PHOTO_ID:3274155842706395}}