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 java.util.*;
public class A{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine());
        String s[] = in.nextLine().split(" ");
        int a[] = new int[s.length];
        for (int i = 0; i < s.length; i++) {
            a[i] = Integer.parseInt(s[i]);
        }
        Map<Long,Long> map = new HashMap<Long,Long>();
        long sum = 0;
        for (int i = 0; i < n; i++) {
            long x = a[i], y = 1;
            while (y < x) {
                y *= 2;
            }
            while (y <= 2000000000) {
                long z = y - x;
                if (map.get(z) != null) {
                    sum += map.get(z);
                }
                y *= 2;
            }
            if (map.get(x) == null) {
                map.put(x, (long)1);
            } else {
                map.put(x, map.get(x) + 1);
            }
        }
        System.out.println(sum);
    }
}