Welcome to ZOJ Contests Information Problems Runs Statistics Ranklist Clarification 104 - The 11th Zhejiang University Programming Contest - G
Gaussian Prime

Time Limit: 3 Seconds      Memory Limit: 65536 KB

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 ≤ x1x2 ≤ 100, -100 ≤ y1y2 ≤ 100.

Output

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

```3
0 0 0 0
0 0 0 10
0 3 0 3
```

```0/1
2/11
7/16
```

References

Author: Local Contests 2011 Committee
Contest: The 11th Zhejiang University Programming Contest
Submit    Status