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 Main {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    Map<Long, Long> a = new HashMap<>();
    long[] p = new long[] {1,         2,        4,         8,         16,
                           32,        64,       128,       256,       512,
                           1024,      2048,     4096,      8192,      16384,
                           32768,     65536,    131072,    262144,    524288,
                           1048576,   2097152,  4194304,   8388608,   16777216,
                           33554432,  67108864, 134217728, 268435456, 536870912,
                           1073741824};
    long m = 0, ans = 0;
    int n = in.nextInt();

    for (int i = 0; i < n; i++) {
      long v = in.nextLong();

      for (int j = 0; j < p.length && p[j] <= m + v; j++)
        if (p[j] < v)
          continue;
        else if (a.containsKey(p[j] - v))
          ans += a.get(p[j] - v);

      m = Math.max(m, v);
      a.put(v, (a.get(v) == null ? 0 : a.get(v)) + 1);
    }

    System.out.format("%d\n", ans);
  }
}
