2484: Multiplication table

Teacher Mai has a multiplication table in base p.

For example, the following is a multiplication table in base 4:

But a naughty kid maps numbers 0..p-1 into another permutation and shuffle the multiplication table.

For example Teacher Mai only can see:

Teacher Mai wants you to recover the multiplication table. Output the permutation number 0..p-1 mapped into.

It's guaranteed the solution is unique.

There are multiple test cases, terminated by a line "0".

For each test case, the first line contains one integer p(2<=p<=500).

In following p lines, each line contains 2*p integers.The (2*j+1)-th number x and (2*j+2)-th number y in the i-th line indicates equation i*j=xy in the shuffled multiplication table.

Warning: Large IO!

For each case, output one line.

First output "Case #k:", where k is the case number counting from 1. The following are p integers, indicating the permutation number 0..p-1 mapped into.

4
2 3 1 1 3 2 1 0
1 1 1 1 1 1 1 1
3 2 1 1 3 1 1 2
1 0 1 1 1 2 1 3
0

Case #1: 1 3 2 0