You are given n integers a1, a2, ..., an. Find the number of pairs of indexes i, j (i < j) that ai + aj is a power of 2 (i. e. some integer x exists so that ai + aj = 2x).

Input

The first line contains the single positive integer n (1 ≤ n ≤ 105) — the number of integers.

The second line contains n positive integers a1, a2, ..., an (1 ≤ ai ≤ 109).

Output

Print the number of pairs of indexes i, j (i < j) that ai + aj is a power of 2.

Examples

Input

4
7 3 2 1


Output

2


Input

3
1 1 1


Output

3

Note

In the first example the following pairs of indexes include in answer: (1, 4) and (2, 4).

In the second example all pairs of indexes (i, j) (where i < j) include in answer.
import bisect


def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    a.sort()

    # powers
    p = list()
    p.append(2)
    for i in range(1, 32):
        p.append(p[i - 1]*2)

    res = 0
    for i in range(0, n):
        for j in p:
            x = j - a[i]
            if x <= 0:
                continue
            ai = bisect.bisect_left(a, x, i + 1, n)
            if ai != n:
                if a[ai] == x:
                    bi = bisect.bisect_right(a, x, i + 1, n)
                    res += (bi - ai)
    print(res)


main()
