Bactérias

Tadeu foi contratado recentemente para trabalhar no mais novo laboratório de biologia de sua universidade. Sua primeira tarefa consiste em estudar a taxa de reprodução de um determinado tipo de bactérias.

Tadeu iniciou seu experimento com uma única bactéria e descobriu que as bactérias se reproduzem a cada dia que passa. Mais especificamente, a cada dia, cada bactéria no recipiente de Tadeu se transforma em $P$ bactérias, onde $P$ é um inteiro positivo que Tadeu denominou como fator de multiplicação das bactérias.

Tadeu gostaria de obter a maior quantidade de bactérias possível, mas ele não pode deixar que essa quantidade ultrapasse a capacidade de $N$ bactérias do recipiente, pois isso invalidaria todo o seu experimento. Observe que a quantidade de bactérias pode ser exatamente igual a $N$ e isso não invalida o estudo de Tadeu.

Por exemplo, em um experimento cuja bactéria tem fator de multiplicação $P = 2$ e a capacidade do recipiente é $N = 32$:

• no início do experimento há apenas $1$ bactéria;
• após $1$ dia haverá $1 \cdot P = 2$ bactérias;
• após $2$ dias haverá $2 \cdot P = 4$ bactérias;
• após $3$ dias haverá $4 \cdot P = 8$ bactérias;
• após $4$ dias haverá $8 \cdot P = 16$ bactérias;
• após $5$ dias haverá $16 \cdot P = 32$ bactérias, o que excede a capacidade $N = 30$ do recipiente.

Nesse caso, Tadeu pode deixar as bactérias se reproduzindo por no máximo $4$ dias.

Dados o fator de multiplicação $P$ e a capacidade $N$ do recipiente, ajude Tadeu a determinar durante quantos dias ele pode deixar as bactérias se reproduzindo sem que a quantidade de bactérias exceda a capacidade do recipiente.

Entrada

A entrada é composta de duas linhas, cada uma contendo um único inteiro. A primeira linha contém $N$, a capacidade do recipiente. A segunda linha contém $P$, o fator de multiplicação das bactérias.

Saída

Seu programa deverá imprimir uma única linha, contendo apenas um inteiro, a quantidade máxima de dias que Tadeu pode deixar as bactérias se reproduzindo sem invalidar seu experimento.

Restrições

• $2\leq P\leq N\leq 30\ 000$

Informações sobre a pontuação

A tarefa vale 100 pontos. Estes pontos estão distribuídos em subtarefas, cada uma com suas restrições adicionais às definidas acima.

• Subtarefa 1 (0 pontos): Esta subtarefa é composta apenas pelos exemplos mostrados abaixo. Ela não vale pontos, serve apenas para que você verifique se o seu programa imprime o resultado correto para os exemplos.
• Subtarefa 2 (50 pontos): $P=2$ e $N\leq 100$.
• Subtarefa 3 (50 pontos): Sem restrições adicionais.

Seu programa pode resolver corretamente todas ou algumas das subtarefas acima (elas não precisam ser resolvidas em ordem). Sua pontuação final na tarefa é a soma dos pontos de todas as subtarefas resolvidas corretamente por qualquer uma das suas submissões.

Exemplo de Entrada 1

30
2

Exemplo de Saída 1

4

Exemplo de Entrada 2

20000
5

Exemplo de Saída 2

6

Exemplo de Entrada 3

49
7

Exemplo de Saída 3

2