A. Sequence with Digits

链接：https://codeforces.com/contest/1355/problem/A

Let's define the following recurrence:

an+1=an+minDigit(an)⋅maxDigit(an).an+1=an+minDigit(an)⋅maxDigit(an).

Here minDigit(x)minDigit(x) and maxDigit(x)maxDigit(x) are the minimal and maximal digits in the decimal representation of xx without leading zeroes. For examples refer to notes.

Your task is calculate aKaK for given a1a1 and KK.

Input

The first line contains one integer tt (1≤t≤10001≤t≤1000) — the number of independent test cases.

Each test case consists of a single line containing two integers a1a1 and KK (1≤a1≤10181≤a1≤1018, 1≤K≤10161≤K≤1016) separated by a space.

Output

For each test case print one integer aKaK on a separate line.

Example

input

Copy

output

Copy

Note

a1=487a1=487

a2=a1+minDigit(a1)⋅maxDigit(a1)=487+min(4,8,7)⋅max(4,8,7)=487+4⋅8=519a2=a1+minDigit(a1)⋅maxDigit(a1)=487+min(4,8,7)⋅max(4,8,7)=487+4⋅8=519

a3=a2+minDigit(a2)⋅maxDigit(a2)=519+min(5,1,9)⋅max(5,1,9)=519+1⋅9=528a3=a2+minDigit(a2)⋅maxDigit(a2)=519+min(5,1,9)⋅max(5,1,9)=519+1⋅9=528

a4=a3+minDigit(a3)⋅maxDigit(a3)=528+min(5,2,8)⋅max(5,2,8)=528+2⋅8=544a4=a3+minDigit(a3)⋅maxDigit(a3)=528+min(5,2,8)⋅max(5,2,8)=528+2⋅8=544

a5=a4+minDigit(a4)⋅maxDigit(a4)=544+min(5,4,4)⋅max(5,4,4)=544+4⋅5=564a5=a4+minDigit(a4)⋅maxDigit(a4)=544+min(5,4,4)⋅max(5,4,4)=544+4⋅5=564

a6=a5+minDigit(a5)⋅maxDigit(a5)=564+min(5,6,4)⋅max(5,6,4)=564+4⋅6=588a6=a5+minDigit(a5)⋅maxDigit(a5)=564+min(5,6,4)⋅max(5,6,4)=564+4⋅6=588

a7=a6+minDigit(a6)⋅maxDigit(a6)=588+min(5,8,8)⋅max(5,8,8)=588+5⋅8=628a7=a6+minDigit(a6)⋅maxDigit(a6)=588+min(5,8,8)⋅max(5,8,8)=588+5⋅8=628

虽然是1200的题，但本菜鸡还是t了一发（不读题的后果QAQ）

代码：

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <limits>
#include <list>
#include <map>
#include <iomanip>
#include <ios>
#include<iosfwd>
#include <iostream>
#include <istream>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <vector>
#include <cwchar>
#include <cwctype>
#define ll long long
#define rep(i,a,n) for(int i=a;i<=n;i++)
using namespace std;
ll n,m,t,k;
ll a[1000001];
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>n>>k;
		m=n;
		for(int i=1;i<k;i++)
		{
			n=m;
			ll min1=10,max1=-1;
			while(n)
			{
				min1=min(min1,n%10);
				max1=max(max1,n%10);
				n/=10;
			}
			m=m+min1*max1;
			if(min1==0)
			break;
		}
		cout<<m<<endl;
		
	}
}