If you go through history you will come across many fun facts about the capital city of a country. In many countries the most famous or most populated or most industrialized cities are not declared capital. For example, Zurich or Geneva is not capital of Switzerland it is Berne. In Australia the capital is neither Melbourne nor Sydney, it is Canberra and guess what Canberra was built to be capital! In Brazil Brasilia is capital not Rio. Head of your country decided to redesign the capital. Dr. Krakow is appointed as the head architect of this project. Having been in Europe and America, he has vast experience about city life. He wants to lay roads like New York. That is, if you see from above, it will look like a big 2d grid. He wants to build the parliament at (0, 0) coordinate of this grid. After that, he asks some people where would they love to stay. Of course, it is not possible to allow to build homes anywhere the people like. There are many constraints to consider. One of the constraints is the parliament has to be at the optimal position. A position is optimal if summation of Manhattan distance to all the houses from the position is minimum. For example, suppose there are three proposals to build houses at following positions: (1, 1), (−1, −1) and (2, 2). If Dr. Krakow approves to build houses at (1, 1) and (−1, −1) then (0, 0) would be optimal position. But if he approves (1, 1) and (2, 2) then (0, 0) is no more optimal position. Please note, there may be many optimal positions for some set of approval, but (0, 0) has to be one of them. Given some proposals, help Dr. Krakow to figure out number of ways he can approve some of the proposals so that parliament is at one of the optimal positions. Please note, there may be request for the same place from different persons. In such case Dr. Krakow can approve none or all or some of these proposals. When computing summation of Manhattan distance, all of the approved proposals are counted, that is, if there are two approved proposals at the same place, then distance from this place to the parliament will be counted twice. Input The first line of the input will contain a positive integer T (T ≤ 5). Hence T cases follow. First line of the test case contains number of proposals n (1 ≤ n ≤ 105). Hence n liness follow, each describing a proposal x, y (−109 ≤ x, y ≤ 109 and xy ̸= 0). Output For each case print case number followed by space separated n numbers where i-th of these numbers denotes number of ways you can accept i proposals. Since the answer can be very big you need to present the solution in modulo 7340033. Sample Input 2 3 -1 -1 11 22 4 11 -1 1
2/2 1 -1 -1 -1 Sample Output Case 1: 020 Case 2: 0201