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

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

Input

• Dòng đầu chứa số nguyên dương \(T\) (\(T \leq 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\%\) số điểm): \(L < R \leq 10^6\).
• Subtask \(2\) (\(30\%\) số điểm): \(R - L \leq 10^6\).
• Subtask \(3\) (\(30\%\) số điểm): Không có ràng buộc nào thêm.