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

public class PowersOFtwo {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		Map<Long, Long> count = new HashMap<Long, Long>();
		long ans = 0;
		for(int i=0;i<n;i++){
			long x = sc.nextLong();
			long y = 1;
			while(y < x){
				y *= 2;
			}
			while(y <= 2000000000){
				long z = y - x;
				if(count.get(z) != null){
					ans += count.get(z);
				}
				y *= 2;
			}
			if(count.get(x) == null){
				count.put(x, 1l);
			}
			else{
				count.put(x, count.get(x) + 1);
			}
		}
		System.out.println(ans);
	}
}