FBR3DWA

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class D {
    FastScanner in;
    PrintWriter out;

    static final boolean USE_DOWNLOADS_FOLDER = true;

    List<Integer> buildChain(int[] a, int root) {
        List<Integer> res = new ArrayList<>();
        while (true) {
            boolean ok = false;
            for (int i = 0; i < a.length; i++) {
                if (a[i] == root) {
                    res.add(i);
                    root = i;
                    ok = true;
                    break;
                }
            }
            if (!ok) {
                break;
            }
        }
        return res;
    }

    class Chain {
        int len;
        boolean connectsToFirst;
        boolean connectsToSecond;

        public Chain(int len, boolean connectsToFirst, boolean connectsToSecond) {
            this.len = len;
            this.connectsToFirst = connectsToFirst;
            this.connectsToSecond = connectsToSecond;
        }
    }

    void solve() {
        int tc = in.nextInt();
        for (int t = 0; t < tc; t++) {
            System.err.println("test: " + t + "/" + tc);
            int n = in.nextInt();
            int[] a = new int[n];
            int[] b = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = in.nextInt() - 1;
                b[i] = in.nextInt() - 1;
            }
            int q0ans = 0;
            for (int i = 0; i < n; i++) {
                if (a[i] == b[i]) {
                    q0ans++;
                }
            }
            List<Integer> first = buildChain(a, n);
            List<Integer> second = buildChain(a, n + 1);
            List<Integer> firstExpected = buildChain(b, n);
            List<Integer> secondExpected = buildChain(b, n + 1);
            long[] res = new long[n + 2];
            for (int q = 0; q <= 2 && q <= n; q++) {
                for (int c = 0; c <= n; c++) {
                    int[][] prec = null;
                    if (q == 1 && first.size() <= c && second.size() <= c && n <= 2 * c) {
                        int stay = Math.max(0, n - c);
                        int alrScore = 0;
                        boolean[] canShuffle = new boolean[n];
                        Arrays.fill(canShuffle, true);
                        for (int i = 0; i < stay; i++) {
                            int myId = first.get(i);
                            canShuffle[myId] = false;
                            int realNextId = i == 0 ? n : (first.get(i - 1));
                            if (b[myId] == realNextId) {
                                alrScore++;
                            }
                        }
                        for (int i = 0; i < stay; i++) {
                            int myId = second.get(i);
                            canShuffle[myId] = false;
                            int realNextId = i == 0 ? (n + 1) : (second.get(i - 1));
                            if (b[myId] == realNextId) {
                                alrScore++;
                            }
                        }
                        boolean[] hasPrevCanShuffle = new boolean[n];
                        for (int i = 0; i < n; i++) {
                            if (canShuffle[i] && b[i] < n) {
                                hasPrevCanShuffle[i] = true;
                            }
                        }
                        List<Chain> allChains = new ArrayList<>();
                        int firstLast = stay == 0 ? n : first.get(stay - 1);
                        int secondLast = stay == 0 ? (n + 1) : second.get(stay - 1);
                        for (int i = 0; i < n; i++) {
                            if (!canShuffle[i]) {
                                continue;
                            }
                            if (hasPrevCanShuffle[i]) {
                                continue;
                            }
                            int cur = i;
                            int len = 0;
                            while (cur < n && canShuffle[cur]) {
                                cur = b[cur];
                                len++;
                            }
                            boolean endFirst = cur == firstLast;
                            boolean endSecond = cur == secondLast;
                            allChains.add(new Chain(len, endFirst, endSecond));
                        }
                        int[] dp = new int[c + 1];
                        int[] ndp = new int[c + 1];
                        Arrays.fill(dp, Integer.MIN_VALUE / 2);
                        dp[0] = alrScore;
                        for (Chain chain : allChains) {
                            Arrays.fill(ndp, Integer.MIN_VALUE / 2);
                            for (int curLenF = 0; curLenF < dp.length; curLenF++) {
                                int cur = dp[curLenF];
                                if (cur < 0) {
                                    continue;
                                }
                                for (int useLen = 0; useLen <= chain.len; useLen++) {
                                    int addScore = Math.max(useLen - 1, 0);
                                    int useLenRigth = chain.len - useLen;
                                    addScore += Math.max(useLenRigth - 1, 0);
                                    if (useLen > 0 && chain.connectsToFirst) {
                                        addScore++;
                                    }
                                    if (useLenRigth > 0 && chain.connectsToSecond) {
                                        addScore++;
                                    }
                                    int nLen = curLenF + useLen;
                                    if (nLen < ndp.length) {
                                        ndp[nLen] = Math.max(ndp[nLen], cur + addScore);
                                    }
                                }
                            }
                            int[] tmp = dp;
                            dp = ndp;
                            ndp = tmp;
                        }
                        prec = new int[c + 1][c + 1];
                        for (int i = 0; i < prec.length; i++) {
                            Arrays.fill(prec[i], -1);
                        }
                        for (int lenFirst = 0; lenFirst < dp.length; lenFirst++) {
                            int realLenFirst = lenFirst + stay;
                            int realLenSecond = n - realLenFirst;
                            if (realLenSecond > c || realLenFirst > c) {
                                continue;
                            }
                            prec[realLenFirst][realLenSecond] = Math.max(prec[realLenFirst][realLenSecond], dp[lenFirst]);
                            if (prec[realLenFirst][realLenSecond] > n) {
                                throw new AssertionError();
                            }
                        }
                        for (int i = 0; i < prec.length; i++) {
                            for (int j = 0; j < prec[i].length; j++) {
                                int cur = prec[i][j];
                                if (i + 1 < prec.length) {
                                    prec[i + 1][j] = Math.max(prec[i + 1][j], cur);
                                }
                                if (j + 1 < prec[i].length) {
                                    prec[i][j + 1] = Math.max(prec[i][j + 1], cur);
                                }
                            }
                        }
                    }
                    for (int x = 0; x <= c; x++) {
                        for (int y = 0; y <= c; y++) {
                            long multiplier = q < 2 ? 1 : (n - 2 + 1);
                            multiplier *= x < c ? 1 : (n - c + 1);
                            multiplier *= y < c ? 1 : (n - c + 1);
                            int v = -1;
                            boolean badInitState = first.size() > c || second.size() > c || n > 2 * c || n > x + y;
                            if (!badInitState) {
                                if (q == 0) {
                                    if (first.size() <= x && second.size() <= y) {
                                        v = q0ans;
                                    }
                                } else if (q == 1) {
                                    v = prec[x][y];
                                } else {
                                    if (firstExpected.size() <= x && secondExpected.size() <= y) {
                                        v = n;
                                    } else {
                                        v = n - 1;
                                    }
                                }
                            }
                            if (v > n) {
                                throw new AssertionError();
                            }
                            res[v + 1] += multiplier;
                        }
                    }
                }
            }
            out.print("Case #" + (t + 1) + ":");
            for (long r : res) {
                out.print(" " + r);
            }
            out.println();
        }
    }


    void run() {
        try {
            if (USE_DOWNLOADS_FOLDER) {
                File inFile = getLatestFilefromDir("/Users/bminaiev/Downloads");
                System.err.println("WILL USE FILE: " + inFile.toString());
                in = new FastScanner(inFile);
            } else {
                in = new FastScanner(new File("A.in"));
            }
            out = new PrintWriter(new File("D.out"));

            solve();

            out.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    private File getLatestFilefromDir(String dirPath) {
        File dir = new File(dirPath);
        File[] files = dir.listFiles();
        if (files == null || files.length == 0) {
            return null;
        }

        File lastModifiedFile = files[0];
        for (int i = 1; i < files.length; i++) {
            if (lastModifiedFile.lastModified() < files[i].lastModified()) {
                lastModifiedFile = files[i];
            }
        }
        return lastModifiedFile;
    }

    void runIO() {

        in = new FastScanner(System.in);
        out = new PrintWriter(System.out);

        solve();

        out.close();
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(File f) {
            try {
                br = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        public FastScanner(InputStream f) {
            br = new BufferedReader(new InputStreamReader(f));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return null;
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

        boolean hasMoreTokens() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return false;
                st = new StringTokenizer(s);
            }
            return true;
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    public static void main(String[] args) {
        new D().run();
    }
}