В древньому Єгипті були дроби тільки з чисельником, рівним одиниці, дроби виду 1/n, так звані аліквотні дроби і ще був дріб 2/3. Дроби з чисельником, відмінним від одиниці, записували як суму аліквотних дробів, наприклад: 2/5 = 1/5 + 1/5, 2/7 = 1/4 + 1/28.

   Задано деякі натуральні P, Q, A та N. Скільки існує способів представити дріб P/Q у вигляді суми аліквотних дробів так, щоб кількість доданків не перевищувала N, а добуток знаменників А? Перестановки доданків вважаються одним способом.

   Наприклад, то й же вище згадуваний унікальний єгипетський дріб 2/3, при умові, що задані P, Q, A, N рівні відповідно 2, 3, 120, 3 можна представити 4-ма наступними способами при допомозі аліквотних дробів:

   Вхідні дані

   Кожен тест складається з декількох тестових випадків, кількість яких не перевищує 200. У кожному вхідному рядку через пропуск задано чотири числа P, Q, A та N.

   0 <= P, Q <= 800, 0 <= A <= 12000, 0 <= N <= 7.

   Останні чотири числа в тесті 0, 0, 0, 0 є ознакою закінчення тестових даних.

   Вихідні дані

   Для кожного тестового випадку в окремому рядку вивести відповідь на поставлену задачу.