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 math
import sys

def main():
  powers_of_two = set()
  for i in range(1, 36):
    powers_of_two.add(2**i)
  n = int(input())
  a = map(int, raw_input().split())
  numbers_in_array = {}
  for x in a:
    if x in numbers_in_array:
      numbers_in_array[x] += 1
    else:
      numbers_in_array[x] = 1
  out = 0
  for num in numbers_in_array:
    for power in powers_of_two:
      if power - num in numbers_in_array and power - num == num:
        out += numbers_in_array[num] * (numbers_in_array[num] - 1)
      elif power - num in numbers_in_array:
        out += numbers_in_array[num] * numbers_in_array[power - num]

  print out / 2


if __name__ == '__main__':
  main()
