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.
n = int(input())
a = [int(x) for x in input().split()]

b = {}
for t in a:
    if t in b:
        b[t] += 1
    else:
        b[t] = 1

dva =[]
for i in range(31):
    dva.append(2**i)

m = 0
for d in dva:
    for k in b.keys():
        if (k < d):
            if not k == d // 2:
                if d - k in b:
                    m += b[k] * b[d - k]
            else:
                m += b[k] * (b[k] - 1)
                
print(m // 2)

