Valid pairs

A famous Italian restaurant allows guests to enter only if they are present in pairs and the sum of the wealth of the people of the pair is a power of $3$. A group of people wants to eat at the restaurant. Mathematically, if there are two people of wealth $a$ and $b$, it forms a valid pair if $a+b=3^k$ for some positive integer $k$. They want to know how many possible pairs would be allowed entry.

Input

The first line contains number of guests $n(1\le n\le 10^5)$. The second liine contains the individual wealth $a_1,a_2,...,a_n(1\le a_i\le 3^{20})$ of $n$ people.

Output

Print the number of valid pairs. It is known that:

• One person can be in multiple valid pairs.

• A pair of person $x$ and $y$ is the same as a pair of person $y$ and $x$.

Examples