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

\[ \operatorname{fib}(n) = \begin{cases} a & \text{nếu } n = 1 \\ b & \text{nếu } n = 2 \\ \operatorname{fib}(n-1) + \operatorname{fib}(n-2) & \text{nếu } n \geq 3 \end{cases} \]

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

Dữ liệu vào

• Dòng đầu chứa số nguyên dương \(T\) (\(T \le 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\).

Dữ liệu ra

• 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.

Input 1

2
1 1 1 3
1 1 3 3

Output 1

4
2

Subtask

• Subtask 1 (40 điểm): \(L \lt R \le 10^6\)
• Subtask 2 (30 điểm): \(R - L \le 10^6\)
• Subtask 3 (30 điểm): Không có ràng buộc nào thêm.

Input 1

2
1 1 1 3
1 1 3 3

Output 1

4
2