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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;

public class B { 

	public static long powersOfTwo(int [] a) { 
		HashMap<Integer, Integer> T = new HashMap<Integer, Integer>();

		for(int i=0; i<a.length; i++) { 
			Integer count = T.get(a[i]);

			if(null == count) count = 0;
			
			count += 1;
			T.put(a[i], count);
		}

		ArrayList<Integer> pows = new ArrayList<>();

		long pow = 2; 
		while(pow <= 2000000000) { 
			pows.add((int)pow);
			pow *= 2;
		}

		long totalNumber = 0;
		// O(log(MAX_INT)*N))
		for(int elem : a) { 
			for(Integer p : pows) { 
				if(p-elem > 0) { 
					Integer count = T.get(p-elem);
					if(count != null) { 
						totalNumber += count;
						if(p-elem == elem) totalNumber--;
					}
				}
			}
		}

		return totalNumber/2;
	}
	
	public static void main(String [] args) throws IOException { 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tokenizer;
		
		int N = Integer.parseInt(br.readLine());
		tokenizer = new StringTokenizer(br.readLine());
		int [] a = new int[N];
		for(int i=0; i<N; i++) { 
			a[i] = Integer.parseInt(tokenizer.nextToken());
		}
		
		long sol = powersOfTwo(a);
		System.out.println(sol);
	}
	
}