NGM - A Game with Numbers

no tags 

Nikifor and Trofim play the following game: they write some positive integer smaller than 2,000,000,000 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 positive 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.


hide comments
nonushikhar: 2015-10-02 21:34:42

ac in one go ! extremely easy one! :)

jyotman94: 2015-09-19 21:22:30

DON'T READ THE COMMENTS... SPOILERS!!!

bunnycoder: 2015-09-11 10:05:25

the digit should be from number???
Please Provide some more test cases.

NIKHIL KUMAR SINGH: 2015-08-30 17:58:20

TRUE......@joydeeodas123 and @Manishi Goel ....the comments are seriously the spoilers ....altough I was lucky to read them later

joydeepdas123: 2015-08-30 00:07:15

This is crazy !!! No need to to go through the ques even ,simply going through the comments question can be answered...let others think ...stop spoiling

suhas: 2015-08-25 20:52:24

thought for few minutes... and then it hit me. simple one. :)

coder_shishir: 2015-08-22 21:12:15

solved in one go....excellent problem.....

simarsher220: 2015-08-18 07:33:32

please can someone give me some more test cases

devesh upadhyay: 2015-08-11 09:10:52

easy one ;-p

Manishi Goel: 2015-08-03 13:10:57

spoilers everywhere :(
Let others think


Added by:Roman Sol
Date:2006-05-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ZCon 2007