A digit in a sequence

★★★★★

2.1

12 votes

, Implementation, Algorithms, Basics of Implementation, Binary Search, Math

Details

Submissions

Discussion

Editorial

Problem

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$

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

In the first case, the infinite sequence of numbers for $a = 3, b = 5$ is --> $(3,8,13,18,23,28,...)$ . The long line is $3813182328...$ .

$K^{th}$ digit is 2

In the second case, the infinite sequence of numbers for $a = 2, b = 7$ is --> $(2,9,16,23,30,37,...)$ . The long line is $2916233037...$ .

$K^{th}$ digit is 7