Valid pairs#11454
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 . A group of people wants to eat at the restaurant. Mathematically, if there are two people of wealth and , they form a valid pair if a + b = 3^k for some positive integer . They want to know how many possible pairs would be allowed entry.
The first line contains number of guests n\:(1 \le n \le 10^5). The second line contains the individual wealth a_1, a_2, ..., a_n\:(1 \le a_i \le 3^{20}) of people.
Print the number of valid pairs. It is known that:
One person can be in multiple valid pairs.
A pair of person and is the same as a pair of person and .
Example 1