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.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

public class Main 
{

	public static void main(String[] args)
	throws IOException
	{
		Reader r = new Reader();

		ArrayList<Integer> power = new ArrayList<>();
		int ans = 1;
		for (int i=1;i < 32;++i)
			power.add(ans = ans << 1);

		r.readLine();
		int n = r.readInt(0);

		r.readLine();
		ArrayList<Integer> vals = new ArrayList<Integer>();
		for (int i=0;i < n;++i)
			vals.add(r.readInt(i));

		Collections.sort(vals);

		HashMap<Integer,Pair> last = new HashMap<Integer,Pair>();
		int co = 1;
		for (int i=1;i < n;++i)
			if (vals.get(i - 1).equals(vals.get(i)))
				++co;
			else
			{
				last.put(vals.get(i - 1), new Pair(co, i - 1));
				co = 1;
			}
		last.put(vals.get(n - 1), new Pair(co, n - 1));

		long res = 0;
		co = 0;
		
		for (int i=0;i < n;++i)
		{
			int v1 = vals.get(i);
			for (int j=0;j < 31;++j)
			{
				int v2 = power.get(j);
				int df = v2 - v1;
				int id = Collections.binarySearch(vals, df);

				if (id > -1)
				{
					Pair temp = last.get(df);
					int freq = temp.f;
					int lIdx = temp.s;
					
					if (df == v1)
					{
						res += lIdx - i;
					}
					else
					{
						co += freq;
					}
					
				}
			}
		}
		
		System.out.println(co/2+res);
		r.close();
	}
}


class Pair implements Comparable<Pair>
{
	int f,s;

	public Pair()
	{}

	public Pair(int f, int s)
	{
		this.f = f;
		this.s = s;
	}

	@Override
	public String toString()
	{
		// TODO: Implement this method
		return f + " " + s;
	}

	@Override
	public int compareTo(Pair o)
	{
		// TODO: Implement this method
		if (f == o.f)
			return s - o.s;
		return f - o.f;
	}
}

class Reader
{
	private BufferedReader reader;
	private String line[];

	public Reader()
	{
		reader = new BufferedReader(
			new InputStreamReader(System.in));
	}

	public void readLine()
	throws IOException
	{
		line = reader.readLine().split(" ");
	}

	public int readInt(int pos)
	throws IOException
	{
		return Integer.parseInt(line[pos]);
	}

	public double readDouble(int pos)
	throws IOException
	{
		return Double.parseDouble(line[pos]);
	}

	public long readLong(int pos)
	throws IOException
	{
		return Long.parseLong(line[pos]);
	}

	public String readString(int pos)
	throws IOException
	{
		return line[pos];
	}

	public void close()
	throws IOException
	{
		reader.close();
	}
}