All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
As New Year is approaching, Salik is studying functions in order to sharpen his math skills. Instead of regular functions, he is studying a strange function F which operates on non-negative integers. The value of F(A) is obtained by the following process:
- Compute the sum of digits of A; let's denote this sum by S.
- If S is a single-digit integer, then F(A) = S.
- Otherwise, F(A) = F(S).
It's guaranteed that this process correctly defines the function F.
Since this problem was pretty straightforward, he invented a new problem: Given two integers A and N, compute F(AN). Can you help him solve this task?
- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first and only line of each test case contains two space-separated integers A and N.
For each test case, print a single line containing one integer — the value of F(AN).
- 1 ≤ T ≤ 105
- 1 ≤ A, N ≤ 1018
Subtask #1 (10 points):
- 1 ≤ N ≤ 3
- 1 ≤ A ≤ 105
Subtask #2 (20 points):
- 1 ≤ N ≤ 100
- 1 ≤ A ≤ 105
Subtask #3 (70 points): original constraints
Input: 3 5 2 7 2 127 1 Output: 7 4 1
Example case 1: F(5 · 5) = F(25) = F(2+5) = F(7) = 7
Example case 2: F(7 · 7) = F(49) = F(4+9) = F(13) = F(1+3) = F(4) = 4
Example case 3: F(127) = F(1+2+7) = F(10) = F(1+0) = F(1) = 1
|Tags||abx_2109, fast-expo, ltime55, observations, simple|
|Time Limit:||0.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.