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\)