# Gaussian Prime

Time Limit: Java: 3000 ms / Others: 3000 ms

Memory Limit: Java: 65536 KB / Others: 65536 KB

## Description

In number theory, a Gaussian integer is a complex number whose real and imaginary part are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as Z[i]. The prime elements of Z[i] are also known as Gaussian primes. Gaussian integers can be uniquely factored in terms of Gaussian primes up to powers of i and rearrangements.

A Gaussian integer a + bi is a Gaussian prime if and only if either:

• One of a, b is zero and the other is a prime number of the form 4n + 3 (with n a nonnegative integer) or its negative -(4n + 3), or
• Both are nonzero and a2 + b2 is a prime number (which will not be of the form 4n + 3).

0 is not Gaussian prime. 1, -1, i, and -i are the units of Z[i], but not Gaussian primes. 3, 7, 11, ... are both primes and Gaussian primes. 2 is prime, but is not Gaussian prime, as 2 = i(1-i)2.

Your task is to calculate the density of Gaussian primes in the complex plane [x1, x2] × [y1, y2]. The density is defined as the number of Gaussian primes divided by the number of Gaussian integers.

## Input

There are multiple test cases. The first line of input is an integer T ≈ 100 indicating the number of test cases.

Each test case consists of a line containing 4 integers -100 ≤ x1 ≤ x2 ≤ 100, -100 ≤ y1 ≤ y2 ≤ 100.

## Output

For each test case, output the answer as an irreducible fraction.

## Sample Input

3
0 0 0 0
0 0 0 10
0 3 0 3

## Sample Output

0/1
2/11
7/16

References

http://en.wikipedia.org/wiki/Gaussian_integer
Weisstein, Eric W. "Gaussian Prime." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/GaussianPrime.html

None

## Source

The 11th Zhejiang University Programming Con