1610: Summing Arithmetic Progressions

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 L and R, inclusive, can be represented as the sum of some magic arithmetic progression with exactly k elements?

The input will contain several test cases. The first line in the input contains the number of test cases N. The following N lines contain three integers L, R (1 ≤ L ≤ R ≤ 1000000000), k (2 ≤ k ≤ 5).

For each test case, output two integers on a separate line, representing how many integers between L and R, can be represented as the sum of some magic arithmetic progression with exactly k elements.

5
1 12 3
1 10 2
20 30 4
1 9 4
1 13 4

3
8
6
0
1

1. 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. 2. Every number except 1 and 2 is representable: 3=1+2, 4=1+3, 5=1+4, etc. 3. The representable numbers are 20, 22, 24, 26, 28 and 30. 4. The minimal possible sum is 1+2+3+4=10. 5. And the next possible sum is 2+3+4+5=14.