Sum of Digits (Recursive)

Background

Congcong is currently learning about recursion. He encountered an interesting problem that requires calculating the sum of digits of a non-negative integer, but it must be done recursively, without using loops.

Problem Description

Given a non-negative integer $n$, return the sum of its digits recursively (no loops). Note that modulo (% 10) by $10$ yields the rightmost digit (e.g., $126 \% 10$ is $6$), while integer division (/ 10) by $10$ removes the rightmost digit (e.g., $126 / 10$ is $12$).

Input Format

Input is given from Standard Input in the following format.

A non-negative integer $n$.

Output Format

Output is printed to Standard Output in the following format.

The sum of the digits of $n$.

Sample

126

9

49

13

12

3

Sample Explanation

For input $126$: The last digit of $126$ is $6$ ($126 \% 10 = 6$). The remaining part is $12$ ($126 / 10 = 12$). Recursively calculate the sum of digits for $12$, which is $3$. The final result is $6 + 3 = 9$.

Constraints

$0 \le n < 2^{31}$. Time limit: $1$ second, Memory limit: $1024$ MiB.