Ones

Time limit1sMemory limit128 MB

Summary

Given p and n, count how many times 2 and 3 divide the repunit 1 + p + ... + p^(n-1) in base p.

Level: Hard8 of 10
Topics: Number theory, Math
Solved: No attempts yet

Problem

Let $a$ be the natural number whose representation in base $p$ consists of the digit $1$ repeated $n$ times in a row. In other words,

$a = \underbrace{11\cdots1}_{n} = 1 + p + p^2 + \cdots + p^{n-1} = \sum_{i=0}^{n-1} p^{i}$

Find the greatest exponents of $2$ and of $3$ that divide $a$ . That is, write a program that finds the largest integer $x$ with $2^{x} \mid a$ and the largest integer $y$ with $3^{y} \mid a$ .

Input

The first line contains two natural numbers $p$ and $n$ separated by a space. ( $1 < p < 10^9$ , $1 \le n < 10^9$ )

Output

Print two non-negative integers separated by a space: the greatest exponent $x$ of $2$ that divides $a$ , followed by the greatest exponent $y$ of $3$ that divides $a$ .

Examples2

Example 1
Input
```
17 2
```
Expected output
```
1 2
```
Example 2
Input
```
10 4
```
Expected output
```
0 0
```