题目描述
Mehta was doing his usual office work when all of a sudden, he refreshes his Gmail. It contained the mail of his not so old friend who was still jobless and asking Mehta for a certain help. His Friend Verma had applied for a certain hiring challenge for some certain company. So, Verma gave Mehta a link of the contest which contained the following question. So, you being a colleague of Mehta decide to help him with his friend's task.
Task:
Given three integers A, B and K, you need to report the K^th number between A and B(both inclusive), satisfying the property that: the number does not contain a digit 'zero' and product of digits of number is a perfect square. If there doesn't exist that K^th number output "-1"(without quotes).
Input:
First Line contains the number of test cases T.
Next T lines contain 3 space separated integers A, B, K as mentioned in the task.
Output:
Output T lines as answer for every test case.
Constraints:
1 ≤ T ≤ 100
1 ≤ A ≤ B ≤ 10^18
1 ≤ K ≤ 10^7
SAMPLE INPUT
3
1 10 4
8 14 2
1 1000 23
SAMPLE OUTPUT
-1
11
119
Explanation
Sample Case#1: {1,4,9} are the only numbers that satisfy above property, so there is no 4th number, hence answer is -1.
Sample Case#2: {9,11,14} are three numbers in range [8,14] which have product of digits as perfect square, so, 2nd number in range [8,14] will be 11.
输入格式
见题面
输出格式
见题面