### Problem Statement

Given a positive integer number, concatenate one or more copies of number to create an integer that is divisible by k. Do not add any leading zeroes. Return the least number of copies needed, or -1 if it is impossible.

### Definition

 Class: ConcatenateNumber Method: getSmallest Parameters: int, int Returns: int Method signature: int getSmallest(int number, int k) (be sure your method is public)

### Constraints

-number will be between 1 and 1,000,000,000, inclusive.
-k will be between 1 and 100,000, inclusive.

### Examples

0)

 `2` `9`
`Returns: 9`
 At least 9 copies are needed, since 222222222 is divisible by 9.
1)

 `121` `11`
`Returns: 1`
 121 is divisible by 11.
2)

 `1` `2`
`Returns: -1`
 You can never get an even number by concatenating only 1's.
3)

 `35` `98765`
`Returns: 9876`
 The resulting integer could be really big.
4)

 `1000000000` `3`
`Returns: 3`

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=11124&pm=8589

srbga

#### Testers:

PabloGilberto , Olexiy , Andrew_Lazarev , ivan_metelsky

#### Problem categories:

Brute Force, Math, Simple Math