시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB16021284120181.479%

문제

키파는 곱하기를 좋아한다. 그래서 키파는 수를 보면 각 자리 숫자를 모두 곱해서 하나의 수를 만든다. 키파는 기쁘다. 키파는 이 작업을 계속해서 반복한다. 그런데 수가 한 자리가 되었다. 키파는 슬퍼졌다.

키파의 기쁨이 지속될 수 있는 것이 몇 단계인지를 출력하는 프로그램을 작성하시오. 예를 들어 679라면:

  • 679 → 6*7*9 = 378 (1단계)
  • 378 → 3*7*8 = 168 (2단계)
  • 168 → 1*6*8 = 48 (3단계)
  • 48 → 4*8 = 32 (4단계)
  • 32 → 3*2 = 6 (5단계: 키파는 슬퍼졌다.)

키파는 5단계만에 슬퍼지므로 5를 출력하면 된다.

입력

각각의 입력은 하나의 테스트 케이스로 이루어진다. 입력은 첫 번째 줄에 선행하는 0이 없는 9자리 이하의 수가 하나 주어진다.

출력

각각의 입력에 대해 키파의 기쁨이 지속될 수 있는 단계의 수를 출력하라. 

예제 입력 1

5

예제 출력 1

0

예제 입력 2

10

예제 출력 2

1

예제 입력 3

679

예제 출력 3

5
W3sicHJvYmxlbV9pZCI6IjExNjQ4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjOWMwXHVjMThkIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQwYTRcdWQzMGNcdWIyOTQgXHVhY2YxXHVkNTU4XHVhZTMwXHViOTdjIFx1Yzg4Ylx1YzU0NFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViNzk4XHVjMTFjIFx1ZDBhNFx1ZDMwY1x1YjI5NCBcdWMyMThcdWI5N2MgXHViY2Y0XHViYTc0IFx1YWMwMSBcdWM3OTBcdWI5YWMgXHVjMjJiXHVjNzkwXHViOTdjIFx1YmFhOFx1YjQ1MCBcdWFjZjFcdWQ1NzRcdWMxMWMgXHVkNTU4XHViMDk4XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWI5Y2NcdWI0ZTBcdWIyZTQuIFx1ZDBhNFx1ZDMwY1x1YjI5NCBcdWFlMzBcdWMwNThcdWIyZTQuIFx1ZDBhNFx1ZDMwY1x1YjI5NCBcdWM3NzQgXHVjNzkxXHVjNWM1XHVjNzQ0IFx1YWNjNFx1YzE4ZFx1ZDU3NFx1YzExYyBcdWJjMThcdWJjZjVcdWQ1NWNcdWIyZTQuJm5ic3A7XHVhZGY4XHViN2YwXHViMzcwIFx1YzIxOFx1YWMwMCBcdWQ1NWMgXHVjNzkwXHViOWFjXHVhYzAwIFx1YjQxOFx1YzVjOFx1YjJlNC4gPHN0cm9uZz5cdWQwYTRcdWQzMGNcdWIyOTQgXHVjMmFjXHVkMzdjXHVjODRjXHViMmU0PFwvc3Ryb25nPi48XC9wPlxyXG5cclxuPHA+XHVkMGE0XHVkMzBjXHVjNzU4Jm5ic3A7XHVhZTMwXHVjMDY4XHVjNzc0IFx1YzljMFx1YzE4ZFx1YjQyMCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWJhODcgXHViMmU4XHVhY2M0XHVjNzc4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IDY3OVx1Yjc3Y1x1YmE3NDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT42NzkmbmJzcDsmcmFycjsgNio3KjkgPSAzNzggKDFcdWIyZThcdWFjYzQpPFwvbGk+XHJcblx0PGxpPjM3OCAmcmFycjsgMyo3KjggPSAxNjggKDJcdWIyZThcdWFjYzQpPFwvbGk+XHJcblx0PGxpPjE2OCZuYnNwOyZyYXJyOyAxKjYqOCA9IDQ4ICgzXHViMmU4XHVhY2M0KTxcL2xpPlxyXG5cdDxsaT40OCZuYnNwOyZyYXJyOyA0KjggPSAzMiAoNFx1YjJlOFx1YWNjNCk8XC9saT5cclxuXHQ8bGk+MzImbmJzcDsmcmFycjsgMyoyID0gNiAoNVx1YjJlOFx1YWNjNDogPHN0cm9uZz5cdWQwYTRcdWQzMGNcdWIyOTQgXHVjMmFjXHVkMzdjXHVjODRjXHViMmU0PFwvc3Ryb25nPi4pPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVkMGE0XHVkMzBjXHViMjk0IDVcdWIyZThcdWFjYzRcdWI5Y2NcdWM1ZDAgXHVjMmFjXHVkMzdjXHVjOWMwXHViYmMwXHViODVjIDVcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM3ODVcdWI4MjVcdWM3NDAgXHVkNTU4XHViMDk4XHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NDAgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMTIwXHVkNTg5XHVkNTU4XHViMjk0IDBcdWM3NzQgXHVjNWM2XHViMjk0IDlcdWM3OTBcdWI5YWMgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzIxOFx1YWMwMCBcdWQ1NThcdWIwOTggXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM3ODVcdWI4MjVcdWM1ZDAgXHViMzAwXHVkNTc0IFx1ZDBhNFx1ZDMwY1x1Yzc1OCBcdWFlMzBcdWMwNjhcdWM3NzQgXHVjOWMwXHVjMThkXHViNDIwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViMmU4XHVhY2M0XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTE2NDgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQZXJzaXN0ZW5jZSIsImRlc2NyaXB0aW9uIjoiPHA+Q29uc2lkZXIgdGhlIHNlcmllcyBvZiBudW1iZXJzIHdoZXJlIGVhY2ggdGVybSBpcyB0aGUgcHJvZHVjdCBvZiB0aGUgZGVjaW1hbCBkaWdpdHMgb2YgdGhlIHByZXZpb3VzIHRlcm0uIEV2ZW50dWFsbHkgdGhlIHRlcm0gd2lsbCBiZSByZWR1Y2VkIHRvIGEgc2luZ2xlIGRpZ2l0LjxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSBzdGFydCB3aXRoIDY3OTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT42Nzk6IDYqNyo5ICZyYXJyOyAzNzg8XC9saT5cclxuXHQ8bGk+Mzc4OiAzKjcqOCAmcmFycjsgMTY4PFwvbGk+XHJcblx0PGxpPjE2ODogMSo2KjggJnJhcnI7IDQzPFwvbGk+XHJcblx0PGxpPjQ4OiA0KjggJnJhcnI7IDMyPFwvbGk+XHJcblx0PGxpPjMyOiAzKjIgJnJhcnI7IDY8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGUgbnVtYmVyIG9mIHN0ZXBzIHRoaXMgdGFrZXMgaXMgY2FsbGVkIHRoZSBQZXJzaXN0ZW5jZSBvZiBhIG51bWJlci4gVGh1cywgdGhlIHBlcnNpc3RlbmNlIG9mIDY3OSBpcyA1LCBzaW5jZSB0aGF0JnJzcXVvO3MgbnVtYmVyIG9mIHN0ZXBzIGl0IHRvb2sgdG8gZ2V0IHRvIGEgc2luZ2xlIGRpZ2l0IG51bWJlci48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkVhY2ggaW5wdXQgd2lsbCBjb25zaXN0IG9mIGEgc2luZ2xlIHRlc3QgY2FzZS4gTm90ZSB0aGF0IHlvdXIgcHJvZ3JhbSBtYXkgYmUgcnVuIG11bHRpcGxlIHRpbWVzIG9uIGRpZmZlcmVudCBpbnB1dHMuIFRoZSBpbnB1dCB3aWxsIGNvbnNpc3Qgb2YgYSBzaW5nbGUgbGluZSwgd2l0aCBhIHBvc2l0aXZlIG51bWJlciBvZiB1cCB0byA5IGRlY2ltYWwgZGlnaXRzIHdpdGggbm8gbGVhZGluZyB6ZXJvcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBhIHNpbmdsZSBpbnRlZ2VyLCByZXByZXNlbnRpbmcgdGhlIHBlcnNpc3RlbmNlIG9mIHRoZSBpbnB1dCBudW1iZXI7IHRoYXQgaXMsIHRoZSBudW1iZXIgb2Ygc3RlcHMgbmVjZXNzYXJ5IHRvIHJlZHVjZSBpdCB0byBhIHNpbmdsZSBkaWdpdC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d