Unit Fraction Partition

分子が1であり分母が正整数である分数を単位分数と呼ぶ． 正の有理数 p/q を有限個の単位分数の和として表現したものを， p/q の単位分数への「分割」と呼ぶ． 例えば， 1/2 + 1/6 は 2/3 の単位分数への分割である． 足し算の順序の違いは無視する． 例えば， 1/6 + 1/2 を 1/2 + 1/6 と区別しない．

与えられた四つの正整数 pと qと aと n に対して， p/q の単位分数への分割で以下の二つの条件を満たすものの個数を数えなさい．

• 分割は n個以下の単位分数の和である．
• 分割に含まれる単位分数の分母の積は a 以下である．

例えば， (p,q,a,n) = (2,3,120,3) ならば， 4と報告しなければならない．なぜならば，

で，条件を満たす分割が尽くされるからである．

Input

入力は，1000個以下のデータセットの並びで，その後に終端行が続く．

データセットは四つの正整数 p と q と a と n を含む行で， p,q <= 800 かつ a <= 12000 かつ n <= 7 を満たす． それらの整数は空白で区切られる．

終端行は，空白で区切られた四つのゼロを含むちょうど1行で構成される． これは入力データの一部ではなく，入力終了を表す印（しるし）である．

Output

出力は各行に一つの整数がある何行かで構成されなければならない． その他の文字は出力中に出現してはならない．

データセット p, q, a, n に対応する出力の整数は p/q の n個以下の単位分数への分割で，単位分数の分母の積が a 以下となるものをすべて数えた個数でなければならない．

Sample Input

2 3 120 3
2 3 300 3
2 3 299 3
2 3 12 3
2 3 12000 7
54 795 12000 7
2 3 300 1
2 1 200 5
2 4 54 2
0 0 0 0

Output for the Sample Input

4
7
6
2
42
1
0
9
3

---