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

public class PowerOfTwo {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = sc.nextInt();

		long count = 0;
		int[] h = new int[30];
		for (int i = 0; i < 30; i++)
			if (i == 0) h[i] = 2;
			else h[i] = h[i - 1] * 2;

		HashMap<Integer, Integer> m = new HashMap<>();
		for (int i = 0; i < n; i++) {
			for (int j = 1; j < 31; j++) 
				if (m.containsKey(h[j - 1] - a[i]))
					count += m.get(h[j - 1] - a[i]);
			if (m.containsKey(a[i]))
				m.put(a[i], m.get(a[i]) + 1);
			else
				m.put(a[i], 1);
		}
		System.out.println(count);
	}
	static boolean isPower(int n) {
		return (n & (n - 1)) == 0;
	}
}
