Background

Special for beginners, ^_^

Description

小明最近在自学化学，并对天平产生了浓厚的兴趣，于是从实验室借来一台天平。小明发现，这台天平配的砝码都是某个正整数K（2<=K<=6）的非负整数幂次，并且砝码没有相同的质量。假设砝码只能放在天平的右边。问能准确称量的第n（1<=n<=3e7）小的物体的质量多少？.

Format

Input

每行（不超过1万行）两个正整数包含两个整数n和K。

Output

每行一个整数，表示答案。

Samples

5 3
1 3

10
1

Limitation

1s, 1024KiB for each test case.