Mali Đole je sinoć sanjao dva broja: ~S~ i ~K~. Iznenada se probudio, i odmah zapisao dve definicije koje su mu pale na pamet:

• Slepi brojevi su oni brojevi čija je suma cifara jednaka ~S~.
• Klepi par čine dva Slepa broja čiji je proizvod deljiv sa ~K~.

Da bi se Đole ponovo uspavao, on želi da prebroji koliko ima Klepih parova, koje čine neka dva Slepa broja iz intervala ~[A,B]~. Brzo je shvatio da ovakvih parova može imati mnogo, pa vas je zamolio za pomoć da mu brzo kažete kako bi odmoran stigao na takmičenje iz enigmatike.

Opis ulaza

Prva linija standardnog ulaza sadrži četiri prirodna broja broj ~A, B, S~ i ~K~ odvojena razmakom.

Opis izlaza

U prvu i jedinu liniju standardnog izlaza ispisati ukupan broj Klepih parova koje čine neka dva Slepa broja iz intervala ~[A,B]~.

Primer 1

Ulaz

1 100 3 9

Izlaz

10

Primer 2

Ulaz

80 120 15 6

Izlaz

2

Objašnjenje primera

U prvom primeru Slepi brojevi iz datog intervala su: ~3,12,21~ i ~30~ (svi brojevi od ~1~ do ~100~ čija je suma cifara ~3~). Parovi Slepih brojeva čiji je proizvod deljiv sa ~9~ čine Klepe brojeve, i u ovom slučaju imamo ~10~ takvih parova: ~(3,3), (3,12), (3,21), (3,30), (12,12), (12,21), (12,30), (21,21), (21,30), (30,30).~

U drugom primeru imamo dva Slepa broja: ~87~ i ~96~, i dva Klepa para: ~(87,96), (96,96)~.

Ograničenja

U svim test primerima važi: ~1 \leq S \leq 100~, i ~B \geq A \geq 1~, i ~K \geq 1~.

Test primeri su podeljeni u ~4~ disjunktne grupe:

• U test primerima vrednim 25 poena: ~A,B,K \leq 10000~.
• U test primerima vrednim 30 poena: ~A,B \leq 10^6~, i ~K \leq 10000~.
• U test primerima vrednim 35 poena: ~A,B,K \leq 10^6~.
• U test primerima vrednim 10 poena: ~A,B \leq 10^{12}~, i ~B-A \leq 10^6~, i ~K \leq 10^6~.