F. Repeating b-ary
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Trying to get out of Rabbit's house through the ground hole, Pooh got stuck in that hole. Christopher Robin said they should wait for Pooh to get thin. In order to sustain Pooh, Christopher Robin suggested him to write down $$$b$$$-ary representation of $$$\frac{1}{x}$$$. By the time Winnie-the-Pooh finishes his writings, he will surely get thin. How long will it take depends on the number of digits in non-periodic part and the number of digits in periodic part of $$$b$$$-ary representation. Given $$$x$$$, find these numbers.

Input

The only line contains two integers $$$x$$$ and $$$b$$$ ($$$2 \leq x \leq 10^{12}$$$, $$$2 \leq b \leq 10^{18}$$$) where $$$b$$$ is the base of desired representation.

Output

Output the minimal possible lengths of non-periodic part and periodic part.

Examples
Input
2 10
Output
1 0
Input
3 10
Output
0 1
Input
2 2
Output
1 0
Input
3 2
Output
0 2