Maximum Assignment Profit

You are given \( T \) test cases. For each test case, you are given an integer \( N \) representing the number of developers/projects and an \( N \times N \) profit matrix \( P \) where \( P_{ij} \) is the profit obtained by assigning developer \( i \) to project \( j \). Each developer must be assigned exactly one project and vice-versa.

Your task is to determine the maximum total profit that can be achieved by optimally assigning developers to projects. This optimization problem is equivalent to solving the assignment problem and can be formulated using techniques such as the Hungarian algorithm or using a dynamic programming approach with bitmasking.

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer \( T \), the number of test cases.
• For each test case, the first line contains the integer \( N \), the size of the profit matrix.
• The following \( N \) lines each contain \( N \) space-separated integers representing a row of the profit matrix.

outputFormat

For each test case, output the maximum total profit on a separate line to stdout.

2
3
10 5 2
7 8 5
1 2 5
4
5 9 3 8
7 6 8 10
8 5 6 9
6 9 1 7

23
33