题目背景

黑土地上，一棵小苗破土而出。

几个月里，它吮吸着甘甜的雨露，享受着温暖的阳光，愈发翠绿了起来。

它越长越高，越长越壮，似乎要突破云霄。

它长成了一棵大树，渴望着去天空中，看一看这美丽的世界。

题目描述

请留意本题并不寻常的时空限制。

给定一个数 $x$，用如下规则建立一棵有根树：

• 根节点为 $\lang0,x\rang$。

• 对于一个节点 $\lang i,j\rang$，若 $j < 3$，则它是叶子节点，否则它的子节点为对于任意 $1 \le k$ 且 $j$ 的位数 $\ge k$， $\lang j_k, k\rang$，其中 $j_k$ 为它三进制表示从左向右的第 $k$ 位。

求这棵树的叶子节点的数目。

输入格式

一行两个整数 $p, q$，表示 $x = p^q$。

输出格式

一行一个整数，即为所求。

题目保证答案在 $\tt int64$ 范围内。

9 1

4

27 1

6

提示

本题采用 SubTask 捆绑测试。

对于 $100\%$ 的数据，$p^q \le 3^{3^{35}}$（$10^{10^9} \lt 3^{3^{35} } \lt 10^{2.5 \times 10^9}$），保证 $p = 3^l(l\in \mathbb N^+)$。