Զույգ թվեր
Անուշը շատ է սիրում զույգ թվերով խաղեր հորինել, և մի անգամ նա մի քանի թղթի վրա գրել էր զույգ բնական թվեր։ Նրա եղբայրը նկատել էր այդ թղթերը և սոսնձել իրար այնպես, որ թվերը գրվեցին իրար հետևից՝ կազմելով նոր մեծ թիվ (Օրինակ, 44, 12, 106 -> 4412106)։ Անուշը տեսավ դա, բայց եղբայրն այնքան լավ էր սոսնձել, որ չէր երևում, թե սկզբնական թղթերը որոնք էին։ Անուշի մտքով մի հարց առաջացավ, ամենաշատը քանի՞ զույգ բնական թիվ կարող էր սկզբնապես եղած լինել, որոնք իրար կպցնելով կստացվեր այս նոր թիվը։ Գրեք ծրագիր, որը կօգնի կամայական մուտքային թվի համար պարզել սկզբնական թվերի առավելագույն քանակը, որոնց կցագրման արդյունքում կստացվի մուտքում տրված թիվը։
Մուտքային տվյալներ
Ստանդարտ մուտքում տրված է մեկ թիվ, որը չի գերազանցում -ը։ Երաշխավորվում է, որ այդ թիվը հնարավոր է ստանալ զույգ բնական թվերից կցագրման միջոցով։
Ելքային տվյալներ
Ստանդարտ ելքում պետք է արտածել մեկ թիվ՝ սկզբնական թվերի առավելագույն քանակը։
Օրինակ
Մուտք | Ելք |
|---|---|
4412106 | 5 |
175334 | 1 |
Առաջին օրինակի դեպքում սկզբնական թվերի առավելագույն քանակը 5 է՝ սկզբնական թվերը վերցնելով 4, 4, 12, 10, և 6, կստանանք պահանջվող արդյունքը։
Երկրորդ օրինակի դեպքում միակ հնարավոր տարբերակը մի թիվ վերցնելն է, որը հենց 175334-ն է։
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB