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 Main1 
{

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

		ArrayList<Long> power = new ArrayList<Long>();

		Long num = 1L;

		while (num < 2000000000L)
			power.add(num = num << 1);

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

		r.readLine();
		ArrayList<Long> vals = new ArrayList<Long>();

		for (int i=0;i < n;++i)
		{
			vals.add(r.readLong(i));
		}

		Collections.sort(vals);

		long ans = 0;
		HashMap<Long,Pair> last = new HashMap<>();

		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));

		co = 0;
		for (int i=0;i < n;++i)
		{
			for (int j=0;j < power.size();++j)
			{

				long diff = power.get(j) - vals.get(i);
				int ind=Collections.binarySearch(vals, diff);

				if (ind > -1)
				{
					Pair p = last.get(diff);


					if (!vals.get(i).equals(diff))
					{
						//ans += p.f;
						co += p.f;
					}
					else 
					{
						ans += p.s - i;
					}

				}
			}
		}

		System.out.println(ans+co/2);

		r.close();
	}
}


class 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;
	}

	
}

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();
	}
}