We are given \(Q\) queries in the form of "\(L \space R \space K\)".
For each query you are asked to print the \(k^{th}\) smallest number in the range \(L \) to \(R\) (both inclusively) whose digit sum is a prime number or report (print \(-1\)) if it doesn't exist.
Input Format
- First line of input contains an integer \(Q\).
- Next \(Q\) lines contain three space-separated integers \(L \space R \space K\) denoting the query.
Output Format
For each \(i^{th}\) query, print a single integer denoting the answer to the \(i^{th}\) query.
Constraints
\(1 \le Q \le 500\)
\(1 \le L \le R \le 10^{18} \\1 \le K \le R - L + 1\)
For the first query: The numbers in the range are \([3, 4, 5, 6, 7]\) in which \(3, 5\) and \(7\) are having the digit sum a prime and \(2nd\) of them is \(5\) so we will output \(5\).
For the second query: There is only one number in the range \([6]\) in which none is having the digit sum a prime and \(1st\) of them deesn't exist so we will output \(-1\).
For the third query: The numbers in the range are \([10, 12, 13, 14, 15 ... 100]\) in which \([11, 12, 14, 16, 20, 21, 23, 25, 29, 30, 32, 34, 38, 41,43, ... 98]\) are having the digit sum a prime and \(15th\) ot them is \(43\) so we will output \(43\).
