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.io.*;
import java.util.HashMap;
import java.util.HashSet;
public class Main {
public static void main(String args[])throws IOException
{
	BufferedReader obj=new BufferedReader(new InputStreamReader(System.in));
	int n=Integer.parseInt(obj.readLine());
	String temp[]=obj.readLine().split(" ");
	int arr[]=new int[n];
	for(int i=0;i<n;i++)
	{
		arr[i]=Integer.parseInt(temp[i]);
	}
	HashMap<Integer,Integer> set=new HashMap<>();
	set.put(arr[0],1);
	int maxim=Math.max(Integer.MIN_VALUE,arr[0]);
	long ans=0;
	for(int i=1;i<n;i++)
	{
		int j= (int)(Math.log(arr[i]+maxim)/Math.log(2));
		for(int k=1;k<=j;k++)
		{
			int sum=1<<k;
			if(sum-arr[i]>=0&&set.containsKey(sum-arr[i]))
			{
				ans+=(long)set.get(sum-arr[i]);
			}
		}
		maxim=Math.max(maxim,arr[i]);
		if(set.containsKey(arr[i]))
			set.put(arr[i],set.get(arr[i])+1);
		else
			set.put(arr[i],1);
	}
  System.out.println(ans);	
}
}
