CLEAR - Clear Numbers

Bom has just found a definition of clear numbers as the following: for each positive integer n, we form another number by summing the squares of the digits of n. We repeat this procedure. If at some step, we obtain the number 1 then n is called a clear number. For example, for n=19, we have:

19 → 82 (= 12 +92) → 68 → 100 → 1

Thus, 19 is a clear number.

Not all numbers are clear numbers. For example, for n=12, we have:

12 → 5 → 25 → 29 → 85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89 → 145

Bom is very interested in this definition of clear numbers. He issued a challenge to the landlord: given a positive integer n, find S(n), the clear number succeeding n, i.e. S(n) is the minimum clear number greater than n. However, this question is so easy for the landlord that he challenged Bom with another problem: given two positive integers n and m (1 ≤ n, m ≤ 1015), find the number Sm(n)=S(S(…S(n) )) which is the mth clear number succeeding n.

Please help Bom to solve the task!

Input

The first line contains t (0 < t ≤ 20) , the number of test cases.

Each line in the next t lines contains two positive integers n and m.

Output

Print t lines, each line contains the result of the corresponding test case.

Example

Input
2
18 1
1 145674807	

Output
19
1000000000

Notes

There are 50% of the test cases in which 1 ≤ n, m ≤ 107.


Được gửi lên bởi:Jimmy
Ngày:2009-07-16
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:VNOI Marathon 2009
Round 2
Problem Setter: Đỗ Đức Đông

hide comments
2017-10-09 16:15:27
sao cậu bên dưới lừa tớ
2017-08-21 12:05:51
code brainfuck ne
++++++++++[>+>+++>+++++++>++++++++++<<<<-]>>++.>>++.+++++++++.+++.<<++++++++.>>---------.+++++.++++++.<<--------.>>-----------.<---------.------------.++++++++++.>.<+.+.-----------.+++++++++.>.<<+++++++++++..--.<++++++++++.>---------........>>---.+++++++++.+++.<<++++++++.>>---------.+++++.++++++.<<--------.>>----------.<++.------------.++++++++++.>.<+.+.-----------.+++++++++.>.<<+++++++++++..--.<++++++++++.>---------....>>+++++++++++++++++.<<<++++++++++.>........>>------------------------.<-------------.>----------------------.++++++++++++++.++++++++++++++.------------.--.+++++++++++++++.-------------.<+++++++++++++++.-------------.+++++++++++.<<++++++++++.>........>>+++++++++.+++++++++.+++.<<++++++++.>>---------.+++++.++++++.<<--------.>>---------.<++.------------.++++++++++.>.<+.+.-----------.+++++++++.>.<<+++++++++++..--.<++++++++++.>---------............>>--------.<-------------.>----------------------.++++++++++++++.++++++++++++++.------------.--.+++++++++++++++.-------------.<+++++++++++++++.>++++++.<<++++++++++++++.>++++++++++++++++.>--------.++++++++++++++.------------.--.+++++++++++++++.-------------.<<---.---..>>++++.<<++++++.>.>------.++++++++++++++.------------.--.++++++++++++++++.--------------.<<----.>>+++++.<<++++.>.>-------.++++++++++++++++.--------------.--.+++++++++++++++.-------------.<<---------.>>++++++++++++++++.<<++++.++.>>.<<--.----.>>.<------------------.<<++++++++++.>-----....>>++++++++++++++++.<<<++++++++++.>....>>-----------.-------------.+++++++++++++++.+.---.----.<<.>>-----------.<.
2017-06-17 10:40:01
1 đấm ac, bài thầy đông easy;

Last edit: 2017-06-17 10:40:44
2017-06-16 05:10:36
trâu cũng ac
2017-01-15 04:47:50 tomatoxanh
A/e cho tôi hỏi làm thế nào để đưa bài tập lên đây nhỉ
2016-12-08 04:41:58 le tuan dung
Tôi là Lê Tuấn Dũng. Xin chào các fan hâm mộ.
2016-11-03 15:13:21
Code pascal:
http://shink.in/SKr3P
2016-07-15 17:13:08
bố 13th comment =)))
2015-11-03 23:16:38
Tham khảo : http://www.oni.vn/uR57W

Blog Thuật toán SPOJ (vnspoj) hy vọng giúp mọi người với solution và code hơn 300 bài tại : http://www.oni.vn/uR57W
2015-10-21 16:08:43 Phong
bài thầy Đông @@ ko nhìn cũng biết đệ quy :v
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.