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.Scanner;


public class PowerOfTwo {
	static public void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		long n = sc.nextLong();
		long[] a = new long[(int) n];
		long max_a = 0;
		HashMap<Long, Long> hash = new HashMap<Long, Long>();
		sc.nextLine();
		
		for(int i=0; i<n; i++) {
			a[i] = sc.nextLong();
			max_a = Math.max(a[i], max_a);
			if(hash.containsKey(a[i])) 
				hash.put(a[i], hash.get(a[i])+1);
			else
				hash.put(a[i], 1l);
		}
		Arrays.sort(a);
		
		long ret = 0;
		for(int i=0; i<n; i++) {
			long k = 1;
			while(k-a[i] < a[i]) {
				k*=2;
				long key = k - a[i];
				if(key > 0l && key<a[i] && hash.containsKey(key)) {
					//System.out.println("a: " + a[i]);
					//System.out.println("key:" + key);
					if(key != a[i]) 
						ret += hash.get(key);
					
				}
			}
		}
		
		long key = 1;
		while(key<=max_a) {
			//System.out.println(key);
			if(hash.containsKey(key)) {
				ret += (hash.get(key)*(hash.get(key) - 1))/2;
			}
			key*=2;
		}
		
		System.out.println(ret);
	}
}
