Макс хочет купить новый скейтборд. Он уже посчитал сколько ему нужно денег, чтобы купить новый скейтборд. Оставив калькулятор на полу, он пошёл просить у родителей денег. В это время его маленький брат Юсуф пришёл в комнату и начал нажимать на случайные кнопки калькулятора. К сожалению Макс уже забыл сумму, посчитанную на калькуляторе. Единственное он помнит, что сумма была кратна 4-м.
Вам задана строка s состоящая из цифр (число, которое отображалось на экране калькулятора после того как Юсуф понажимал на случайные кнопки). Ваша задача определить количество подстрок кратных 4-м. Подстрока может начинаться с нуля.
Подстрокой строки называется непустая последовательность подряд идущих символов.
Например, строка 124 содержит четыре подстроки кратные 4-м: 12, 4, 24 и 124. Для строки 04 ответ равен трём: 0, 4, 04.
Рекомендуется для ввода и вывода данных использовать функции gets, scanf, printf в языке C++, поскольку они работают значительно быстрее чем getline, cin, cout. Аналогично, рекомендуется использовать классы BufferedReader, PrintWriter вместо Scanner, System.out в языке Java.
Выходные данные
Выведите целое число a — количество подстрок строки s кратных 4-м.
Обратите внимание, что ответ может быть достаточно большим и не поместиться в 32-битном типе данных. Для сохранения числа вы можете использовать, например, тип long long в языке C++ или тип long в языке Java.