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.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;




public class PowersofTwo {
   
     public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        
        int p[]= new int[32];
        p[0]= 1;
         for (int i = 1; i < 32; i++) {
            p[i]= p[i-1]*2; 
         }
         
         int n = input.nextInt();
         int a[]= new int[n];
         
         Map<Integer, Integer> m = new HashMap<Integer, Integer>();
         
         for (int i = 0; i < n; i++) {
             a[i]= input.nextInt();
             
             if(m.containsKey(a[i]))
                 m.put(a[i], m.get(a[i])+1);
             else
                 m.put(a[i], 1);
             
         }
         
         long count = 0;
         for (int i = 0; i < a.length; i++) {
             for (int j = 1; j < p.length; j++) {
                
                 if(m.containsKey(p[j]-a[i])){
                     count+=m.get(p[j]-a[i]);
                     if(p[j]-a[i]==a[i])count--;
                 }
             }
         }
         System.out.println(count/2);
     }
}
