### Problem Statement

It is a known fact that prime numbers are not evenly distributed. For example, almost all primes give the remainder 1 or 5 when divided by 6 (the only two exceptions are the primes 2 and 3). Your task is to write a program that will help explore this phenomenon.

You will be given three integers: lowerBound, upperBound and modulo. Return the remainder that occurs most often when we take all primes in the set { lowerBound, lowerBound+1, ... upperBound } and divide each of them by modulo. If there are multiple remainders that occur most often, return the smallest of them.

### Definition

 Class: PrimeStatistics Method: mostCommonRemainder Parameters: int, int, int Returns: int Method signature: int mostCommonRemainder(int lowerBound, int upperBound, int modulo) (be sure your method is public)

### Notes

-A prime number is a positive integer that has exactly two divisors. The first few primes are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...

### Constraints

-lowerBound and upperBound are between 1 and 200,000 inclusive.
-lowerBound is less than or equal to upperBound.
-modulo is between 2 and 1000 inclusive.

### Examples

0)

 `3` `14` `5`
`Returns: 3`
 The primes in this interval are: 3, 5, 7, 11 and 13. Their remainders when divided by 5 are 3, 0, 2, 1 and 3, respectively. Thus the most common remainder is 3.
1)

 `3` `33` `1000`
`Returns: 3`
 In this case each of the primes gives a different remainder. According to the tie-breaking rule the smallest of them is returned.
2)

 `25` `27` `17`
`Returns: 0`
 There are no primes in this interval. Each remainder occurs zero times, thus each of them is the most common remainder. Zero is the smallest possible remainder. Thus, according to the tie-breaking rule, zero is returned.
3)

 `1` `200000` `2`
`Returns: 1`
 Almost all primes are odd; the only even prime is 2.
4)

 `1` `1000` `6`
`Returns: 5`
 As mentioned in the introduction, almost all primes give the remainder 1 or 5 modulo 6. In this interval there are more primes of the second kind.

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4661

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=7995&pm=4661

misof

#### Testers:

PabloGilberto , lbackstrom , brett1479 , Olexiy

#### Problem categories:

Simple Math, Simple Search, Iteration