AlgoLiga 2018

Jaś jest wielkim fanem lodów. Lubi lody zarówno w polewie z czarnej jak i z białej czekolady. Lody w białej polewie zawsze je seriami po k sztuk. Jeżeli Jaś zje pod rząd liczbę lodów w białej polewie nie będącą wielokrotnością k to zjedzony deser nie będzie mu smakował.

Dzisiaj naszego bohatera czeka lodowa uczta, mama pozwoli mu kupić pomiędzy a a b dowolnych lodów. Nasz bohater zastanawia się jakie lody powinien kupić i w jakiej kolejności powinien je zjeść, tak żeby mu smakowały. W tym celu chciał wypisać sobie na kartce wszystkie "smakowite" ustawienia. Niestety okazało się, że jest ich strasznie dużo dlatego Jaś poprosił o pomoc Ciebie. Napisz program, który wyznaczy liczbę "smakowitych" ustawień.

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita t ∈ [1;10] określające liczbę zestawów danych. W kolejnych t liniach znajdują się zestawy danych.

Każdy zestaw danych składa się z trzech liczb całkowitych a, b (1 ≤ a ≤ b ≤ 1000) oraz k ∈ [1;1000] opisanych w treści zadania.

Wyjście

Dla każdego zestawu danych należy w osobnej linii wypisać liczbę "smakowitych" ustawień.

Przykład

Wejście:

3
3 4 2
5 5 5
3 4 3

Wyjście:

8
2
5

Wyjaśnienie dla 1 zestawu danych:

Oznaczmy poprzez B loda w białej polewie, zaś poprzez C loda w czarnej polewie. Ustawienia, które będą smakowały Jasiowi to:

1. BBC
2. CBB
3. CCC
4. BBBB
5. BBCC
6. CBBC
7. CCBB
8. CCCC