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

public class Main {
	private static List<Integer> powersOfTwo = new ArrayList<Integer>();

	static {
		int powOfTwo = 1;
		while (powOfTwo > 0) {
			powersOfTwo.add(powOfTwo);
			powOfTwo <<= 1;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		in.readLine();
		String[] lineData = in.readLine().split(" ");
		int[] numbers     = new int[lineData.length];
		Map<Integer, Set<Integer>> indexBuckets = new HashMap<Integer, Set<Integer>>();

		for (int i = 0; i < lineData.length; ++i) {
			numbers[i] = Integer.parseInt(lineData[i]);
			Set<Integer> bucket = indexBuckets.get(numbers[i]);

			if (bucket == null) {
				bucket = new HashSet<Integer>();
				bucket.add(i);

				indexBuckets.put(numbers[i], bucket);
			}
			else 
				bucket.add(i);
		}

		System.out.println(solve(numbers, indexBuckets));
	}

	private static long solve(final int[] nums, final Map<Integer, Set<Integer>> buckets) {
		long count = 0;

		for (int i = nums.length-1; i > 0; --i) {
			int val = nums[i];

			for (int k = 0; k < powersOfTwo.size(); ++k) {
				int powOfTwo  = powersOfTwo.get(k);
				// System.out.printf("val: %d | pow: %d%n", val, powOfTwo);

				if (powOfTwo < val) continue;
				else if (val == powOfTwo) {
					Set<Integer> powBucket = buckets.get(nums[i]);


					count += (powBucket.size()-1);
				}
				else {
					int diff = powOfTwo - val;
					Set<Integer> bucket = buckets.get(diff);

					if (bucket != null && diff != val)
						count += bucket.size();
				}
			}

			buckets.get(val).remove(i);
		}

		return count;
	}
}