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 random
def simulate():
	# n = 100
	n = input()
	arr = map(int, raw_input().split())
	# arr = []
	# for _ in xrange(n):
	# 	arr.append(random.randrange(20))
	# # print arr
	# def is_powers(n):

	# 	while n > 1:
	# 		rem = n%2
	# 		if rem != 0:
	# 			return False
	# 		n /= 2
	# 	return True

	powers_two = [
		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,
		2073741824
	]

	arr.sort()

	def find_two(arr, num):

		start = 0
		end = n - 1

		c = 0
		while start < end:
			# print start, end, num, arr
			if arr[start] + arr[end] == num:

				if arr[start] == arr[end]:
					h = end - start + 1
					c += (h*(h-1))/2
					# print (h*(h-1))/2, start, end
					start = end
				else:
					l = 1
					while arr[start] == arr[start+1]:
						start += 1
						l += 1

					r = 1
					while arr[end] == arr[end-1]:
						end -= 1
						r += 1
					start += 1
					c += l*r
				
			elif arr[start] + arr[end] > num:
				end -= 1
			elif arr[start] + arr[end] < num:
				start += 1
		return c

	def find_sq(arr, power):
		n = len(arr)
		c = 0
		for i in range(n):
			for j in range(i+1, n):
				if arr[i] + arr[j] == power:
					c += 1
		return c

	# a = 0
	a_diff = 0
	for power in powers_two:
		a_diff += find_two(arr, power)
		# a_diff += find_sq(arr, power)
	# if a != a_diff:
		# print a, a_diff
	print a_diff

# for _ in range(500):
simulate()