Bob is writing a program that solves the following problem:

You are given the numbers \(a,b\) to display the infinite sequence of numbers \(a, a + b, a + 2*b, ..., a + N*b, a.. (N+1)*b,... \). Bob has made a mistake, he namely forgot to draw a space for the division between the numbers, resulting in a long line of numbers. In order not to correct the mistake, Bob decided to find out how to find the \(k^{th}\) digit in the formed line (numbering of digits begins with one).

Bob could not find a good solution, so he asks you for help.

Input format

The first line contains a number \(T\) denoting the number of tests.
The first line of each test contains four integers \(a, b, k\).

Output format

Print the \(k^{th}\) digit for each test.

Constraints

\(1 ≤ T ≤ 10 \)

\(1 ≤ a, b ≤ 10^3\)

\( 1 ≤ k ≤ 10^9\)