Макс хочет купить новый скейтборд. Он уже посчитал сколько ему нужно денег, чтобы купить новый скейтборд. Оставив калькулятор на полу, он пошёл просить у родителей денег. В это время его маленький брат Юсуф пришёл в комнату и начал нажимать на случайные кнопки калькулятора. К сожалению Макс уже забыл сумму, посчитанную на калькуляторе. Единственное он помнит, что сумма была кратна 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.