Winnie has run out of backstory to give you, so she just gave you a question instead.

Given a string ~A~ consisting of only integers, find the number of substrings of ~A~ that are divisible by ~9216~.

Input Specification

The first line will contain a string ~A~ ~(1 \le |A| \le 2~ ~000)~. ~A~ will only contain digits, and will not contain leading ~0~s.

Output Specification

Output the number of substrings of ~A~ that are divisible by ~9216~.

Subtasks

Subtask 1 [10%]

~|A| \le 10~

Subtask 2 [20%]

~|A| \le 100~

Subtask 3 [70%]

No further constraints

Sample Input 1

9216

Sample Output 1

1

Sample Input 2

4608046080

Sample Output 1

8