The n-th Fib number can be calculated using the following formula:
fib(n)={aif n=1bif n=2fib(n−1)+fib(n−2)if n≥3
**Task**: Given four positive integers a, b, L, and R (1≤a,b,L,R≤1018), find the last digit of f(n).
#### Input
- The first line contains a positive integer T (1≤T≤105), which is the number of data sets.
- The following T lines each contain four positive integers a, b, L, and R.
#### Output
- Print T lines, each containing a single digit, which is the last digit of f(n) for the corresponding input data set.
#### Example
Input:
211131133
Output:
42
#### Subtasks
- **Subtask 1 (40 points)**: L≤R≤106.
- **Subtask 2 (30 points)**: R−L≤106.
- **Subtask 3 (30 points)**: No additional constraints.
