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 B {
    public static void main(String[] args) {

        // Counter
        int max_Cnt = 0;

        // Input
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
        for(int i=0; i<n; i++){
            int tmp = sc.nextInt();
            if(hashMap.containsKey(tmp)){
                int tmpVal = hashMap.get(tmp);
                tmpVal++;
                hashMap.put(tmp, tmpVal);
                max_Cnt = Math.max(max_Cnt, tmpVal);
            }else{
                hashMap.put(tmp, 1);
            }
        }

        ArrayList<Long> combOfPair = calcCombOfPair(max_Cnt);

        // create the arrayList of the numbers 2^n
        long tmp = 2;
        ArrayList<Integer> arrayList = new ArrayList<Integer>();
        while (tmp < 1e10){
            arrayList.add((int)tmp);
            tmp = tmp*2;
        }

        Set<Integer> set = hashMap.keySet();

        long ans = 0;
        for(int elem: set){
            int cnt = hashMap.get(elem);
            for(int tmpPow2: arrayList){
                if(tmpPow2 <= elem) continue;

                int candidate = tmpPow2 - elem;

                if(elem == candidate){
                    ans += combOfPair.get(cnt);
                }else{
                    if(elem>candidate && hashMap.containsKey(candidate)){
                        int cnt2 = hashMap.get(candidate);
                        ans += cnt* cnt2;
                    }
                }
            }
        }

        System.out.println(ans);

    }

    private static ArrayList<Long> calcCombOfPair(int max_cnt) {
        ArrayList<Long> ret = new ArrayList<Long>();

        ret.add(0L);
        ret.add(0L);

        for(int i=2; i<=max_cnt; i++){
            long tmp = (long) i;
            if(i%2 == 0){
                long n = i / 2;
                ret.add(n * (tmp-1));
            }else{
                long n1 = (tmp-1)/2;
                ret.add(tmp * n1);
            }
        }
        return ret;
    }
}