D. Krosh and powers of two
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Krosh calls positive integer interesting if it can be represented as a sum of two powers of number two, in other words $$$x$$$ is interesting if there exists two non-negative numbers $$$i \ge 0$$$, $$$j \ge 0$$$, $$$i \neq j$$$ such that $$$x = 2^i + 2^j$$$. Krosh has big number $$$m$$$ in binary number system. Length of this number does not exceed $$$2*10^5$$$. Help Krosh to calculate how many interesting numbers there are from $$$1$$$ to $$$m$$$.

Input

In first line you are given number $$$1 \le n \le 2 * 10^5$$$ the length of the number. In second line there is number $$$m$$$ of $$$n$$$ digits in binary system. Every digit is $$$0$$$ or $$$1$$$ and first digit is $$$1$$$.

Examples
Input
4
1010
Output
5
Input
2
11
Output
1