eolymp
bolt
Try our new interface for solving problems
Problems

An aliquot fraction (RU)

An aliquot fraction (RU)

Time limit 1 second
Memory limit 64 MiB

В древнем Египте были дроби только с числителем, равным единице, дроби вида 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-мя следующими способами при помощи аликвотных дробей:

Input data

Каждый тест состоит из нескольких тестовых случаев, количество которых не превышает 200. В каждой входной строке через пробел задано четыре числа P, Q, A и N.

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

Последних четыре числа в тесте 0, 0, 0, 0 являются признаком окончания тестовых данных.

Output data

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

Examples

Input example #1
2 3 120 3
2 3 300 3
2 4 54 2
0 0 0 0
Output example #1
4
7
3