Chữ số

Số fib thứ \(n\) được tính theo công thức :

• \(fib(n) = a\) nếu \(n = 1\)
• \(fib(n) = b\) nếu \(n = 2\)
• \(fib(n) = fib(n - 1) + fib(n - 2)\) nếu \(n > 2\).

Yêu cầu: Cho bốn số nguyên dương \(a\), \(b\), \(L\), \(R\) \((a, b ≤ 10^{18}; L < R ≤ 10^{18})\), hãy tìm chữ số cuối cùng của \(S = fib(L) + fib(L + 1) + ⋯ + fib(R)\).

Input

• Dòng đầu chứa số nguyên dương \(T\) \((T ≤ 100)\) là số bộ dữ liệu;

• Tiếp theo là \(T\) dòng, mỗi dòng chứa bốn số nguyên dương \(a, b, L, R\).

Output

Gồm \(T\) dòng, mỗi dòng ghi ra một chữ số là chữ số cuối cùng của số \(S\) tương ứng với bộ dữ
liệu vào

Example

2
1 1 1 3
1 1 3 3

4
2

Scoring

Subtask \(1\) (\(40\) điểm): \(L < R ≤ 10^6\)

Subtask \(2\) (\(30\) điểm): \(R - L ≤ 10^6\)

Subtask \(3\) (\(30\) điểm): Không có ràng buộc nào thêm