Multiple of Three

Interview

Time limit2sMemory limit128 MB

Summary
Given a huge number as a digit string, repeatedly sum its digits until one digit remains, then report how many steps it took and whether the number is divisible by 3.
Level

Easy3 of 10

Topics
String, Math, Simulation
Solved
No attempts yet

Problem

You are given a large natural number X. Consider the following transformation on X.

  1. Add all digits of the current number.
  2. Replace the current number with that sum.
  3. Repeat the same transformation until the number has exactly one digit.

If the final one-digit value is 3, 6, or 9, then the original number X is a multiple of 3. If it is 1, 2, 4, 5, 7, or 8, then X is not a multiple of 3.

Given X, write a program that finds how many transformations are needed to reach a one-digit number and whether X is a multiple of 3.

Input

The first line contains a large natural number X. X has at most 1,000,000 digits and does not start with 0.

Output

On the first line, output the number of transformations performed. This value must be a non-negative integer.

On the second line, output YES if the given number is a multiple of 3, and NO otherwise.

Hint

1234567 is transformed as 1234567 -> 28 -> 10 -> 1, so the transformation count is 3 and the number is not a multiple of 3.

Examples1

  1. Example 1

    Input
    1234567
    Expected output
    3
NO