Description

有这样一种数列：数列的第一个项已给出，下一项为上一项加上该项的各位数字之和，如数列中第一项为12 则第二项为12+1+2=15；第三项为15+1+5=21；第四项为21+2+1=24 ···一个数列就这样“孵化”出来了。现在要计算孵化数列第n项的值。

Input

输入的第一行为一个整数N，表示后面有N组数据。每组数据中有两个正整数a和n；其中a(a<10000)表示数列的第一项，n(n<1000)表示要求的第n项。

Output

按顺序输出各数列的第n项，每个结果占一行。

Sample

Input

2
12  5
33  9

Output

30
114