SPOJ Problem Set (classical)

1419. A Game with Numbers

Problem code: NGM

Nikifor and Trofim play the following game: they write some integer smaller then 2000000000 and take turns one after another. Nikifor is the first to make a move. The turn is made by the following rule: from the written integer any non-zero digit is subtracted, and the new integer replaces the old one on the desk. For example for integer 40534, the next move can be: 40530, 40531 or 40529. The winner is the player who writes zero on the desk.

Write a program to decide who will win if both players do their best.

Input

The input contains the integer from which the game is started.

Output

In the first line you must write 1 if Nikifor wins and 2 otherwise. If Nikifor wins then in the second line you must output the move in the first turn which guarantees victory for him. If there are many such moves then output any of them.

Example

Input:
14

Output:
1
4

Author: Filimonenkov D.O.

Added by:	Roman Sol
Date:	2006-05-05
Time limit:	1s
Source limit:	50000B
Languages:	All except: CLOJ ERL F# JS PERL 6 TECS
Resource:	ZCon 2007

hide comments


2010-08-05 23:50:33 Vladimir Kirichenkoff Unfair game: Nikifor has much more chances to win! ))
2010-07-27 09:02:36 Mahaboob Ali "The winner is the player who writes zero on the desk". here zeromeans the digit 0 or the number 0 ? i mean if 1 writes say 10 then 1 won the game or the game is still on. till the number on the desk is 0. ? i got it it should be number 0 not digit 0 got ac :) Last edit: 2010-07-27 14:15:36
2010-06-18 18:14:42 kawmia institutes problem setters when should it terminate
2010-03-13 02:30:14 nthrgeek Simple but nice.