### Problem Statement

You are creating a storage management system. This system should create new PLU codes for new items. The requirements state that a PLU code must be a positive integer that does not contain three consecutive equal digits. For example, PLU codes 11211, 73399, 655 and 30 are valid PLU codes, but 11111, 73339, 555 and 3000 are invalid (they contain 111, 333, 555 and 000 respectively). For statistical purposes you want to count the number of invalid PLU codes.

You will be given an int N. You should return the number of invalid PLU codes that are less than N.

### Definition

 Class: PluCodeGenerator Method: countInvalidCodes Parameters: int Returns: int Method signature: int countInvalidCodes(int N) (be sure your method is public)

### Constraints

-N will be between 1 and 1000000000, inclusive.

### Examples

0)

 `111`
`Returns: 0`
 The first invalid PLU code is 111, so there are no invalid PLU codes less than 111.
1)

 `556`
`Returns: 5`
 The invalid PLU codes less than 556 are 111, 222, 333, 444 and 555.
2)

 `1113`
`Returns: 13`
 The invalid PLU codes less than 1113 are 111, 222, 333, 444, 555, 666, 777, 888, 999, 1000, 1110, 1111 and 1112.
3)

 `7346556`
`Returns: 323647`

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=7228&pm=4473

Andrew_Lazarev

#### Testers:

PabloGilberto , lbackstrom , brett1479

#### Problem categories:

Dynamic Programming