MOG
Spanish
|
English

Matcom Online Grader

ACM 2014 - Round #2

Ended

D - Sumando Dígitos

Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)

Continuamente suma los dígitos de un entero positivo N hasta que solamente quede un dígito y luego imprima el resultado. Por ejemplo, si N = 18291 entonces S(N) = 1+8+2+9+1 = 21 y S(S(N)) = 2+1 = 3, por tanto la respuesta es 3. Este problema es muy fácil incluso teniendo N muchas cifras. Para hacerlo más interesante considere las funciones G y H:


Supongamos que k = 1, a = 3 y b = 5, el resultado de evaluar G y H es:

Input

Línea 1 : Un entero T representando la cantidad de casos (1 <= T <= 10^6).
Línea 2…T+1 : Cuatro enteros separados por espacio ki, ai, bi, ti (1 <= ki <= 9, 0 <= ai, bi <= 9, 1 <= ti <= 10^15).

Output

Línea 1...T : Para cada caso imprima un dígito en cada línea representando el resultado de sumar repetidamente los dígitos de H(ti) usando como parámetros ki, ai y bi.

Sample test(s)

Input
2 1 3 5 5 8 5 5 3
Output
3 4

Hints

Hint

Caso 1 : Cuando k = 1, a = 3 y b = 5 se tiene que H(5) = 18921.
Caso 2 : Cuando k = 8, a = 5 y b = 5 se tiene que H(3) = 850, luego S(850) = 13. Como 13 tiene más de un dígito volvemos a sumar sus dígitos, S(13) = 4.