Problems
Valid pairs
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 data
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 data
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
Input example #1
4 1 5 2 4
Output example #1
2