Count Points in a Square with Given Triangular Area Ratios

Given a unit square with vertices A(0,0), B(1,0), C(1,1) and D(0,1), consider an interior point P(x, y). Connecting P to the four vertices partitions the square into four triangles whose areas are proportional to y, 1 - x, 1 - y and x respectively. For a given quadruple of positive integers a, b, c, d the condition is that the set

[ {x, y, 1-x, 1-y} = \left{\frac{2a}{a+b+c+d},; \frac{2b}{a+b+c+d},; \frac{2c}{a+b+c+d},; \frac{2d}{a+b+c+d}\right} ]

as multisets (order not mattering). In other words, after scaling the given ratios by \(k=\frac{2}{a+b+c+d}\), the four numbers \(\frac{2a}{a+b+c+d}\), \(\frac{2b}{a+b+c+d}\), \(\frac{2c}{a+b+c+d}\), \(\frac{2d}{a+b+c+d}\) must appear exactly as \(x, y, 1-x, 1-y\) in some order. Note that the condition is equivalent to partitioning the four scaled numbers into two complementary pairs (each pair summing to 1) where one pair gives \(x\) and \(1-x\) and the other gives \(y\) and \(1-y\).

You are given \(q\) queries. For each query, output the number of distinct points P(x, y) inside the square that satisfy the condition.

inputFormat

The first line contains a positive integer \(q\) representing the number of queries.

Each of the following \(q\) lines contains four positive integers \(a\), \(b\), \(c\), \(d\) separated by spaces.

outputFormat

For each query, output one integer on a separate line – the number of points inside the square that satisfy the condition.

sample

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

1
4
8