## Task
You are given three non negative integers `a`, `b` and `n`, and making an infinite sequence just like fibonacci sequence, use the following rules:
- step 1: use `ab` as the initial sequence.
- step 2: calculate the sum of the last two digits of the sequence, and append it to the end of sequence.
- repeat step 2 until you have enough digits
Your task is to complete the function which returns the `n`th digit (0-based) of the sequence.
### Notes:
- `0 <= a, b <= 9`, `0 <= n <= 10^10`
- `16` fixed testcases
- `100` random testcases, testing for correctness of solution
- `100` random testcases, testing for performance of code
- All inputs are valid.
- Pay attention to code performance.
## Examples
For `a = 7, b = 8 and n = 9` the output should be `5`, because the sequence is:
```
78 -> 7815 -> 78156 -> 7815611 -> 78156112 -> 781561123 -> 7815611235 -> ...
``` 
and the 9th digit of the sequence is `5`.
---
For `a = 0, b = 0 and n = 100000000` the output should be `0`, because all the digits in this sequence are `0`.
# Precompute all 2 digit suffixes into an associated prefix and repeating loop
# E.g. build until we get two repeating values:
#   98 -> [17, 8, 15, 6, 11, 2, 3, 5, 8, 13, 4, 7, 11, 2] (Note: [11, 2] is repeated)
#   -> Prefix '17815611', Loop: '2358134711'
#
# Now any number ending with 98 has a predefined prefix and cycle, e.g.:
#   123 + 598 -> 123598 -> 98 -> Prefix '17815611', Loop: '2358134711'
# Hence 123 + 598 starts with '12359817815611' and then repeats '2358134711' indefinitely

# Dict[str, Tuple[str, str]]
lookup = {}
for i in range(10):
    for j in range(10):
        start = f'{i}{j}'
        n = int(start)
        s = [0, n]
        seen = {}
        while True:
            x = s[-1]
            if x < 10:
                x = x + s[-2] % 10
            else:
                x = (x // 10) + (x % 10)
            
            pair = (s[-1], x)
            if pair not in seen:
                s.append(x)
                seen[pair] = len(s)
            else:
                # idx is the point where prefix finishes and loop starts
                idx = seen[pair] - 1
                prefix = s[2:idx]  # Skip the leading zero and the starting value
                loop = s[idx:]
                lookup[start] = (''.join(map(str, prefix)), ''.join(map(str, loop)))
                break

def find(a, b, n):
    start = f'{a}{b}'[-2:].rjust(2, '0')
    prefix, loop = lookup[start]
    s = str(a) + str(b) + prefix + loop
    
    if n < len(s):
        # Digit in initial supplied digits, the sum of their last two digits or the prefix
        return int(s[n])

    # Digit is in the loop
    m = (n - len(s)) % len(loop)
    return int(loop[m])

# Precompute all 2 digit suffixes into an associated prefix and repeating loop
# E.g. build until we get two repeating values:
#   98 -> [17, 8, 15, 6, 11, 2, 3, 5, 8, 13, 4, 7, 11, 2] (Note: [11, 2] is repeated)
#   -> Prefix '17815611', Loop: '2358134711'
#
# Now any number ending with 98 has a predefined prefix and cycle, e.g.:
#   123 + 598 -> 123598 -> 98 -> Prefix '17815611', Loop: '2358134711'
# Hence 123 + 598 starts with '12359817815611' and then repeats '2358134711' indefinitely

# Dict[str, Tuple[str, str]]
lookup = {}
for i in range(10):
    for j in range(10):
        start = f'{i}{j}'
        n = int(start)
        s = [0, n]
        seen = {}
        while True:
            x = s[-1]
            if x < 10:
                x = x + s[-2] % 10
            else:
                x = (x // 10) + (x % 10)
            
            pair = (s[-1], x)
            if pair not in seen:
                s.append(x)
                seen[pair] = len(s)
            else:
                # idx is the point where prefix finishes and loop starts
                idx = seen[pair] - 1
                prefix = s[2:idx]  # Skip the leading zero and the starting value
                loop = s[idx:]
                lookup[start] = (''.join(map(str, prefix)), ''.join(map(str, loop)))
                break

def find(a, b, n):
    start = f'{a}{b}'[-2:].rjust(2, '0')
    prefix, loop = lookup[start]
    s = str(a) + str(b) + prefix + loop
    
    if n < len(s):
        # Digit in initial supplied digits, the sum of their last two digits or the prefix
        return int(s[n])

    # Digit is in the loop
    m = (n - len(s)) % len(loop)
    return int(loop[m])
