Xiao Ming's climbing record

When Xiaoming arrived at the last island, he came to the mountain interesting.There are many roads in front of Xiaoming. He can choice one road to climb, each road have different uphill and downhill slopes. Each choice of road represents a series of number. such as 12321 road. If Xiao Ming chooses this road. He will climb the mountain at a height of 1->2->3->2-1. And Xiao Ming will gets a sense of pleasure if he climbs his choice. This pleasure is The product of each digit in his choice. If Xiaoming choice the road 12321, we can multiply the number 1*2*3*2*1 = 12. So Xiaoming’s pleasure is 12. Because some road cannot be passed in the mountain.So Xiaoming arrived Mountain Interesting and only can choose the road  is serial number l to r. Xiaoming also has a special habit that the height of mountain must non-decreasing first and non-increasing later.What's more,continuous same height cannot exceed k and the highest point is unique.(Highest point can't be the last.)Can you figure out how much

pleasure XiaoMing can get most？

让你计算l~r之间的数满足某种条件的累积最大值

条件：将这个数每一位数从最高位到最低位拆成以下形式

然后这些数要满足存在一个使得：

最长的连续相等的a不能超过k个

The first line contains a number T indicates T group test (T<=1e4)

For each group

test data consists of three numbers l, r, k (1<=l<=r<=1e18,1<=k<=20).

Output the maximum pleasure that Xiao Ming can get, output 0 if not available

2
22322 22322 1
12321 12321 2

0
12