토모의 계산기

토모의 오래된 계산기에서 가장 특별한 기능은 두 수를 곱한 뒤 = 버튼을 계속 누르면, 현재 표시된 수에 두 번째로 입력한 수가 다시 곱해진다는 것이다. 예를 들어 2와 3을 곱하면 화면에는 6이 나타난다. 이후 =를 더 누를 때마다 18, 54, 162, ...가 차례로 표시된다.

토모는 어떤 수 C가 계산기에 표시된 수의 접미사가 되려면 = 버튼을 모두 몇 번 눌러야 하는지 알고 싶다.

정확히는, 토모가 수 A를 입력하고 * 버튼을 누른 뒤 수 B를 입력하고 = 버튼을 누르면 A와 B의 곱이 화면에 나타난다. 이 첫 번째 = 입력도 횟수에 포함한다. 표시된 수의 끝이 C가 아니면, 끝이 C인 수가 표시될 때까지 = 버튼을 계속 누른다.

수 X의 십진 표기가 수 Y의 십진 표기의 끝부분과 같으면 X를 Y의 접미사라고 한다. 예를 들어 46은 1246의 접미사이지만, 70은 4701의 접미사가 아니다. 계산기는 임의로 많은 자릿수를 처리하고 모든 자릿수를 표시할 수 있다고 가정한다.

A, B, C가 주어졌을 때 = 버튼을 누르는 총 횟수를 구하라.

입력은 한 줄로 이루어지며, 정수 A, B, C가 주어진다.

0 <= A, C <= 100000, 0 <= B <= 1000이다. C의 십진 표기에는 앞에 붙는 0이 없다.

한 줄에 = 버튼을 누르는 총 횟수를 출력한다. 어떤 횟수에서도 C가 표시된 수의 접미사가 되지 않으면 NIKAD를 출력한다.