Um truque bem conhecido para descobrir se um inteiro N é um múltiplo de nove é computar a soma S dos seus dígitos. Se S é um múltiplo de nove, então N também é. Este é um teste recursivo e a profundidade da recursão necessária para obter a resposta para o número N é chamada o grau-9 de N.
Sua tarefa é, dado um inteiro positivo N, determinar se ele é um múltiplo de nove e, caso ele seja, qual o seu grau-9.
A entrada é um arquivo tal que cada linha contém um inteiro positivo. Uma linha contendo o número 0 indica o fim da entrada. Os números fornecidos na entrada possuem até 1000 dígitos. Saída
A saída do programa deve indicar, para cada número da entrada, se ele é um múltiplo de nove e, caso ele seja, o seu grau-9. Veja o exemplo de saída para saber o formato esperado da saída.
999999999999999999999
9
9999999999999999999999999999998
0
999999999999999999999 is a multiple of 9 and has 9-degree 3.
9 is a multiple of 9 and has 9-degree 1.
9999999999999999999999999999998 is not a multiple of 9.