Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_29_04 - Czarno białe

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 ≤ ab ≤ 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

Dodane przez:Maciej Boniecki
Data dodania:2016-08-25
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.