- All Contests
- ProjectEuler+
- Project Euler #230: Fibonacci Words

# Project Euler #230: Fibonacci Words

# Project Euler #230: Fibonacci Words

_{This problem is a programming version of Problem 230 from projecteuler.net}

For any two strings of digits, and , we define to be the sequence (, , , , , ) in which each term is the concatenation of the previous two.

Further, we define to be the -th digit in the first term of that contains at least digits.

Example:

Let , . We wish to find , say.

The first few terms of are:

Then is the -th digit in the fifth term, which is .

You are given triples . For all of them find .

**Input Format**

First line of each test file contains a single integer that is the number of triples. Then lines follow, each containing two strings of decimal digits and and positive integer .

**Constraints**

**Output Format**

Print exactly lines with a single decimal digit on each: value of for the corresponding triple.

**Sample Input 0**

```
2
1415926535 8979323846 35
1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679 8214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196 104683731294243150
```

**Sample Output 0**

```
9
8
```