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 \le 10^{18}\), \(L < R \le 10^{18}\)), hãy tìm chữ số cuối cùng của \(S = fib(L) + fib(L+1) + \dots + fib(R)\).

Input

• Dòng đầu chứa số nguyên dương \(T\) (\(T \le 100\)) là số bộ dữ liệu.
• Tiếp đến 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 đầu vào.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(L < R \le 10^6\).
• Subtask \(2\) (\(30\%\) số điểm): \(R - L \le 10^6\).
• Subtask \(3\) (\(30\%\) số điểm): không có ràng buộc gì thêm.

Example

2
1 1 1 3
1 1 3 3

4
2