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.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
 public class Solution
{
	 private static ArrayList<Long> powers=new ArrayList<Long>();
	
	public static void main(String[] args)
	{
		Scanner sc=new Scanner(System.in);
		prePopulate();
		int n=sc.nextInt();
	
		HashMap<Long,Long> mp=new HashMap<Long,Long>();
		long pairs=0;
		for(int i=0;i<n;i++)
		{
			long curr=sc.nextLong();
			for(Long x:powers)
			{
				if(mp.containsKey(x-curr))
				{
					pairs=pairs+(mp.get(x-curr).intValue());
				}
			}
			long counts=mp.containsKey(curr)?mp.get(curr)+1L:1L;
			mp.put(curr, counts);
			
		}
		
		System.out.println(pairs);
	}
	

	private static void prePopulate() {
		long l=1;
		powers.add(l);
		for(int i=1;i<63;i++)
		{
			l<<=1;
			powers.add(l);
			
		}
		
	}
	
}