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

public class B1 {

	public static Map<Long, Long> input = new LinkedHashMap<>();
	public static Map<Integer, Long> powerOfTwo = new LinkedHashMap<>();

	public static void main(String[] args) {
		long count = 0;
		Scanner in = new Scanner(System.in);
		int inputLength = in.nextInt();
		long arr[] = new long[inputLength];
		for (int i = 0; i < inputLength; i++) {
			arr[i] = in.nextLong();
			if (input.containsKey(arr[i])) {
				count = input.get(arr[i]);
				count++;
			} else {
				count = 1;
			}
			input.put(arr[i], count);
		}
		popPowerOfTwoList();
		solution(input, powerOfTwo);
		in.close();
	}

	public static void popPowerOfTwoList() {
		for (int i = 1; i <= 31; i++) {
			Long val = (long) Math.pow(2, i);
			powerOfTwo.put(i, val);
		}
	}

	public static void solution(Map<Long, Long> input, Map<Integer, Long> pot) {
		long out = 0;
		for (Long l : input.keySet()) {
			for (int i : pot.keySet()) {
				long powTwo = pot.get(i);
				long tmp = powTwo - l;
				if (tmp > l && input.containsKey(tmp)) {
					out = out + (input.get(tmp) * input.get(l));
				} else if (tmp == l) {
					out = out + ((input.get(l) * (input.get(l) - 1)) / 2);
				}
			}
		}
		System.out.println(out);
	}

}