
104  The 11th Zhejiang University Programming Contest  G
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:
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(1i)^{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. InputThere 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. OutputFor each test case, output the answer as an irreducible fraction. Sample Input3 0 0 0 0 0 0 0 10 0 3 0 3 Sample Output0/1 2/11 7/16 References
Author: Local Contests 2011 Committee Contest: The 11th Zhejiang University Programming Contest 