Fastest Clearance

Our many thanks to Clive Fraser for creating this problem!

Ann and Bob are always inventing new games. While looking for things in the attic they came across a large board with a grid of squares, along with a bag of discs. They decided to use these to create a new game. After some discussion, they came up with the following rules.

The board is a square grid of size D. The squares in the grid are referred to by their x,y coordinates. The values of both x and y are in the range 0 to D-1 inclusive. The game starts with a number N of the discs placed randomly on the squares of the board. A single square is allowed to contain more than one disc. A player has to clear the board of discs using the smallest possible number of moves. There are only two allowed moves. The player can select any x-coordinate and remove all discs which are on squares with that x-coordinate. Or, the player can select any y-coordinate and remove all discs which are on squares with that y-coordinate.

When trying out the new game, Ann and Bob made two identical copies of the initial board position. Each of them made a series of moves to clear the board and recorded these so that they could be analysed later. The player who used the smaller number of moves was declared the winner. Ann and Bob enjoyed playing the game but, even after winning a game, wondered how much better they might have done if they had played perfectly.

In this problem you will be given a board of size D x D and the coordinates of N discs placed on the board. You are asked to find the smallest number of moves needed to clear all of the discs from the board.

For the actual problem we will use the Linear Congruential Generator to generate the coordinates of each disc. This has been used before in Code Abbey problems. A random value X(n) is generated using the formula:

X(n) = (A * X(n-1) + C) % M

In this problem we will use the values A = 445, C = 700001 and M = 2097169. Note that % M means the remainder after dividing by the modulus value of M. The value X(n-1) is the previous random value to be generated by this expression. In order to generate the first random value X(1) we need to be given a value for X(0) which is called the seed for the generator. This value will be supplied as part of the data for the problem. The random values X(n) are too large to be used directly, so we will use the following expression to derive an x or y coordinate C from the value X(n):

C = X(n) % D

It should be obvious that this gives a value in the range 0 to D-1, as required.

The following small example should illustrate the problem. We will take N = 15, D = 10 and X(0) = 0. Note that X(0) will not be 0 in the actual problem. We have 15 discs so we need to generate 30 random values. The first 30 random values from the generator are:

700001, 1819434, 840897, 1603084, ..., 1331887, 1988058, 380493, 148697

The first two of these will give us the x,y coordinates (1,4) of the first disc. The second disc has x,y coordinates (7,4) and the 15th disc has x,y coordinates (3,7). The full set of disc coordinates is shown below:

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

One possible way of clearing the board is to choose x-coordinates 0, 1, 3, 6 and 7 with a single y-coordinate of 7. You should be able to verify that every disc matches either one of these x-coordinates or the y-coordinate or both. This clearance has been made in 6 moves. It is not possible to clear this board in less than 6 moves.

In the actual problem, both N and D will always be less than 10^5.

Input/Output description: The first line of the input data will contain a single integer P, the number of puzzles to solve. P lines will follow. Each of these contains three space-separated integers X(0), N and D. For each puzzle, you need to determine the minimum number of moves needed to clear all of the discs from the board. Give your answers as a single string, separated by spaces.

Example:

input:
3
0 15 10
989192 84 80
1065727 872 813 

answer:
6 42 451