Repeated Sequence

Interview

Time limit2sMemory limit256 MB

Summary
Simulate a digit-power sequence until it cycles, then output how many distinct values appear before the repetition starts.
Level

Easy3 of 10

Topics
Simulation, Hash map, Math
Solved
No attempts yet

Problem

Define a sequence D as follows.

  • D[1] = A
  • D[n] is the sum of each digit of D[n-1] raised to the P-th power.

For example, if A = 57 and P = 2, the sequence is 57, 74, 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, ... . Since the values repeat starting from 37, removing the repeating part leaves four numbers: 57, 74, 65, and 61.

Given A and P, find how many numbers remain in the sequence after removing the repeating part.

Input

The first line contains two integers A and P separated by a space.

  • 1 ≤ A ≤ 9999
  • 1 ≤ P ≤ 5

Output

Print the number of values that remain after removing the repeating part of the sequence.

Examples1

  1. Example 1

    Input
    57 2
    Expected output
    4