Kakezan

시간 제한3초메모리 제한512 MB

요약

주어진 정수의 십진 표기를 모든 위치에서 둘로 나눠 곱한 값 중 최댓값을 다음 수로 삼는 과정을 한 자리 수가 될 때까지 반복하고, 그 횟수를 구하거나 무한 반복이면 -1을 출력한다.

문제

太郎君はかけざんを習いたての小学生です。なんとなく、彼はかけざんを気に入っているので、数字を見かけるとかけざんをしたくなります。そんな彼はここのところ、次のような処理を0以上の整数に施すことが好きなようです。 (処理の流れ)

手順1. ある0以上の整数nが10進数表示で一けたならばそこで処理を終了する。そうでなければ手順2に進む
手順2. 10以上の整数nを10進数表示をするとどこかの桁の間に切れ目を入れて二つの数字に分解することが可能である(例えば2012-> 20,12)。このような切り方としてありうるものに対して,得られた二つの数字を掛け合わせて最も大きいものを次のnとして手順1に戻る。(詳しくは下記の"手順2に関する補足を参照")

太郎君はこの処理を気に入っているようですが、何回手順2の操作を繰り返せばよいのか大きい数字だと予想ができず、もしかしたら無限回行われなければならないかもしれないと思っています。そこで、太郎君の兄であり大学生であるあなたに0以上の整数nに対してこの手順2を何回しなければならないかを聞いてきました。

あなたの仕事は、Q個の0以上の整数N1..NQが与えられるので、それぞれの整数で処理の終了までに何回の手順2が施されるかを求めることです。その際にもし無限回の手順が必要ならば、-1を出力してください。

切り分けた結果、桁の初めに0がつくものも考慮に入れる必要があります。例えばn=1024のとき、1*024 , 10*24 , 102*4をそれぞれ計算するとそれぞれ24,240,408となるため、408が選ばれ、これが次のnとなります。

Q
N1
N2
...
NQ

Q個の整数を改行区切りで出力せよ

R1
R2
..
RQ