The hit song "Triple Baka" keeps getting pulled from Spotify, probably because of copyright issues. Hatsune Miku is fed up with this and wants to reunite the gang (Kasane Teto and Akita Neru).

They made a special communication protocol to find each other again, in cases like these.

One of the members must send out a really large number, and the responder must return how many baka numbers there are from 1 to the really large number, inclusive.

A number, n, is baka if, from 1 to n inclusive, all the numbers in the range can be grouped into pairs (a number can only belong to one pair!) to add to a power of 3 (they do not have to be all the same power). If a number is not paired, or any pair is not equal to a power of 3, the number is NOT baka.

Sample Input 0

15

Sample Output 0

3

The numbers 2, 6, and 8 are baka.

The pairings are listed below (all equaling a power of 3):

2: (1,2)
6: (1,2) (3,6) (4,5)
8: (1,8) (2,7) (3,6) (4,5)

It can be shown that no other numbers in the range 1 to 15 fulfill this criteria.

Sample Input 1

2024

Sample Output 1

111