### Problem Statement

We make cardboard boxes. We manufacture a variety of sizes and are concerned that storing them and transporting them will be a problem unless we can nest them into a reasonable number of nested stacks. Each box is a rectangular solid and thus has three side lengths. We say that Box A can be nested in Box B if its smallest length is strictly less than B's smallest length, its 2nd smallest length is strictly less than B's 2nd smallest length, and its largest length is strictly less than B's largest length. No diagonal nesting is allowed.

We have automated the manufacturing process so that random sized boxes are produced. We specify values a, p, and n and the machine produces n boxes with dimensions:

• (a,a^2,a^3) (a^4,a^5,a^6) (a^7,a^8,a^9) ... (a^(3n-2),a^(3n-1),a^(3n))
where a^j denotes (a to the jth power) mod p.

Create a class Nestable that contains a method maxCount that is given the positive integer values a, p, and n and that returns the size of the largest nestable collection of boxes, where a collection is nestable if every pair of boxes from the collection can be nested.

```The sequence of boxes can be generated by
int length=1;
for(int i=0; i<n; i++){
length = (length*a)%p; int x=length;
length = (length*a)%p; int y=length;
length = (length*a)%p; int z=length;
//process this box, which has dimensions x,y,z
}
```

### Definition

 Class: Nestable Method: maxCount Parameters: int, int, int Returns: int Method signature: int maxCount(int a, int p, int n) (be sure your method is public)

### Constraints

-p is between 2 and 2,000,000,000 inclusive
-a is between 1 and p-1 inclusive
-no power of a is divisible by p
-a*p is less than or equal to 2,000,000,000
-n is between 1 and 50,000 inclusive

### Examples

0)

 `10` `15` `3`
`Returns: 1`
 The random generator produces 10, (10*10)%15=10, 10*10%15=10, ... so the three boxes are (10,10,10) (10,10,10) (10,10,10). No pair of boxes is nestable, so the largest nestable collection has size 1.
1)

 `10` `17` `4`
`Returns: 2`
 The sequence is 10, 100%17=15, 150%17=14, 140%17=4, 40%17=6, ... so the 4 boxes are (10,15,14) (4,6,9) (5,16,7) (2,3,13). (4,6,9) nests inside (5,16,7) and there are many other pairs that nest, but there is no sequence of three boxes that can be nested inside each other.
2)

 `10` `100000007` `40000`
`Returns: 1299`
3)

 `93` `21505374` `40000`
`Returns: 151`
4)

 `7` `22` `8`
`Returns: 3`

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4711&pm=1986

dgoodman

#### Testers:

NGBronson , lbackstrom , schveiguy , vorthys

Sorting