|
C |
Corner
the |
Corner
the queen is a game played on n x n chess like board with two players. The rows
and columns are numbered from 0 to n - 1. Then a queen is placed on a random
cell other than (0, 0). Each player
gives one move of the queen towards the cell (0, 0). The move is like a chess
queen. As you know a queen can move any number of cells horizontally,
vertically or diagonally. In Formal a player can move a queen from cell (a1,
b1) to cell (a2, b2) if (a1 = a2 or b1 = b2 or |a1–a2| = |b1–b2|). Moreover in
this game, move that takes queen away from the cell (0, 0) horizontally or
vertically or diagonally is not allowed. Formally, if a player moves queen from
cell (a1, b1) to (a2, b2) then (a2 ≤ a1 and b2 ≤ b1) must be held.
The player who first reaches the cell (0, 0) is the winner. Now you may already
have guessed if both the players play optimally, the starting position
determines the winner. For some cell like (2, 0) player 1 always wins and for
some cell like (1, 2) player 2 always wins.
In
this problem we consider an infinite chess board for playing the game. A
rectangular region is specified. A cell from that region will be picked
randomly as a starting position for the queen. All you have to find is the
probability that player 1 wins assuming that both players will play optimally.
Input
The
first line of input will be a number T (T ≤ 15000) the
number of test cases. Each of the following T lines will contain four
integers x1, y1, x2, y2 (0 ≤ x1 ≤
x2 ≤ 1000000, 0 ≤ y1 ≤ y2 ≤
1000000). Here (x1, y1) is the lower left and (x2, y2)
is the upper right portion of the rectangle. The lowest-leftmost cell is (0, 0)
and it is always outside the given rectangle.
Output
For
each line of input produce one line of output in the format “Board
X: n / d”. Here X is the number of case,
n and d is the numerator and denominator of the probability expressed in
reduced form. See the sample input and output for illustration.
|
Sample Input |
Sample Output |
|
3 |
Board 1: 2 / 3 |
Problem setter: