### Problem Statement

A magic arithmetic progression with k elements is a sequence of the form x, x+d, x+2*d, ..., x+(k-1)*d for some positive integers x and d. How many integers between left and right, inclusive, can be represented as the sum of some magic arithmetic progression with exactly k elements?

### Definition

 Class: SummingArithmeticProgressions Method: howMany Parameters: int, int, int Returns: int Method signature: int howMany(int left, int right, int k) (be sure your method is public)

### Constraints

-left will be between 1 and 1000000000, inclusive.
-right will be between left and 1000000000, inclusive.
-k will be between 2 and 5, inclusive.

### Examples

0)

 `1` `12` `3`
`Returns: 3`
 The representable numbers are: 6=1+2+3, 9=2+3+4=1+3+5, 12=3+4+5=2+4+6=1+4+7. Note that there can be several possible representations for a number.
1)

 `1` `10` `2`
`Returns: 8`
 Every number except 1 and 2 is representable: 3=1+2, 4=1+3, 5=1+4, etc.
2)

 `20` `30` `4`
`Returns: 6`
 The representable numbers are 20, 22, 24, 26, 28 and 30.
3)

 `1` `9` `4`
`Returns: 0`
 The minimal possible sum is 1+2+3+4=10.
4)

 `1` `13` `4`
`Returns: 1`
 And the next possible sum is 2+3+4+5=14.

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10810&pm=8474

Petr

#### Testers:

PabloGilberto , Olexiy , gawry , ivan_metelsky

Simple Math