Напишіть програму, яка знаходитиме кількість натуральних чисел із проміжку ~[a; b]~, які задовольняють одночасно двом таким вимогам:

1. число є точним квадратом, тобто корінь з нього цілий (наприклад, точними квадратами є ~1=1^2~, ~9=3^2~, ~1024=32^2~; а 8, 17, 1000 не є точними квадратами);

2. сума цифр цього числа кратна ~K~ (Наприклад, сума цифр числа 16 рівна ~1+6=7~).

Програма повинна прочитати три числа в одному рядку ~a\,b\,K~ і вивести одне число – кількість чисел, які задовольняють умовам.

Обмеження:

~1\leqslant a\leqslant b\leqslant 2\cdot10^9~,

~2\leqslant K\leqslant 42~.

Вхід

17 222 9

Результат

3

Примітка

Цими трьома числами є 36, 81 і 144. Вивести треба лише кількість 3, але раптом комусь це допоможе зрозуміти, чому їх три…