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.

Task

Given the individual wealth of the people, find the number of valid pairs.

Notes

• 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.

Example

Assumptions

• N = 3
• wealth = [1, 2, 3]

Output

1

Approach

The pair of the first and second person has a sum of wealth of 3 which is a power of 3.

Function description

Complete the function solve provided in the editor. This function takes the following 2 parameters and returns the required answer:

• N: Represents the number of persons
• wealth: Represents an array containing the wealth of the individual people

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

• The first line contains N, the number of persons.
• The second line contains an array wealth, indicating the wealth of the individual people.

Output format

Print a single integer indicating the number of valid pairs.

Constraints

\(1 \le N \le 10^5\)

\(1 \le wealth[i] \le 3^{20}\)