P8308 〈 TREE's OI 2022 Spring 〉Counting By Ternary

On the black soil, a small sprout breaks through the ground. Over several months, it drinks sweet rain and dew, enjoys warm sunlight, and becomes greener and greener.  It grows taller and stronger, as if it is going to reach through the clouds. It grows into a big tree, longing to go into the sky and see this beautiful world. 

**Please note that this problem has unusual time and memory limits.** Given a number $x$, build a rooted tree using the following rules: - The root node is $\lang 0, x \rang$. - For a node $\lang i, j \rang$, if $j < 3$, then it is a leaf node. Otherwise, its children are, for any $1 \le k$ and the number of digits of $j$ is $\ge k$, $\lang j_k, k \rang$, where $j_k$ is the $k$-th digit of the ternary representation of $j$ from left to right. Find the number of leaf nodes of this tree.

One line with two integers $p, q$, meaning $x = p^q$.

One line with one integer, which is the required answer. The problem guarantees that the answer fits in the $\tt int64$ range.

**This problem uses bundled SubTask testing.** | SubTask ID | Score | Special Property | | :-----------: | :-----------: | :-----------: | | $0$ | $10$ | $p \le 3^{15}$, $q = 1$ | | $1$ | $10$ | $p \le 3^{35}$, $q = 1$ | | $2$ | $20$ | $p = 3$, $q \le 3^{15}$ | | $3$ | $60$ | $p = 3$, $q \le 3^{35}$ | For $100\%$ of the testdata, $p^q \le 3^{3^{35}}$ ($10^{10^9} \lt 3^{3^{35}} \lt 10^{2.5 \times 10^9}$), and it is guaranteed that $p = 3^l$ ($l \in \mathbb N^+$). Translated by ChatGPT 5