eolymp
bolt
Try our new interface for solving problems
Problems

Valid pairs

Valid pairs

Time limit 1 second
Memory limit 128 MiB

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