Мали Ђоле је синоћ сањао два броја: \(S\) и \(K\). Изненада се пробудио, и одмах записао две дефиниције које су му пале на памет:

• Слепи бројеви су они бројеви чија је сума цифара једнака \(S\).
• Клепи пар чине два Слепа броја чији је производ дељив са \(K\).

Да би се Ђоле поново успавао, он жели да преброји колико има Клепих парова, које чине нека два Слепа броја из интервала \([A,B]\). Брзо је схватио да оваквих парова може имати много, па вас је замолио за помоћ да му брзо кажете како би одморан стигао на такмичење из енигматике.

Опис улаза

Прва линија стандардног улаза садржи четири природна броја број \(A, B, S\) и \(K\) одвојена размаком.

Опис излаза

У прву и једину линију стандардног излаза исписати укупан број Клепих парова које чине нека два Слепа броја из интервала \([A,B]\).

Пример 1

Улаз

1 100 3 9

Излаз

10

Пример 2

Улаз

80 120 15 6

Излаз

2

Објашњење примера

У првом примеру Слепи бројеви из датог интервала су: \(3,12,21\) и \(30\) (сви бројеви од \(1\) до \(100\) чија је сума цифара \(3\)). Парови Слепих бројева чији је производ дељив са \(9\) чине Клепе бројеве, и у овом случају имамо \(10\) таквих парова: \((3,3), (3,12), (3,21), (3,30), (12,12), (12,21), (12,30), (21,21), (21,30), (30,30).\)

У другом примеру имамо два Слепа броја: \(87\) и \(96\), и два Клепа пара: \((87,96), (96,96)\).

Ограничења

У свим тест примерима важи: \(1 \leq S \leq 100\), и \(B \geq A \geq 1\), и \(K \geq 1\).

Тест примери су подељени у \(4\) дисјунктне групе:

• У тест примерима вредним 25 поена: \(A,B,K \leq 10000\).
• У тест примерима вредним 30 поена: \(A,B \leq 10^6\), и \(K \leq 10000\).
• У тест примерима вредним 35 поена: \(A,B,K \leq 10^6\).
• У тест примерима вредним 10 поена: \(A,B \leq 10^{12}\), и \(B-A \leq 10^6\), и \(K \leq 10^6\).