mehta-and-the-needy-friend

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.

Source: hackerearth | Difficulty: HARD
Tags: Dynamic programming

Sorting


Solutions: