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) + ... + 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

Cho một dãy gồm \(n\) số nguyên dương đôi một khác nhau \(a_1,a_2,...a_n\), một tập \(DSET\) nếu là tập con có lực lượng lớn nhất trong các tập con của tập \(\{a_1,a_2,...,a_n\}\) và nếu \(x\) thuộc tập thì \(2x\) sẽ không thuộc tập.

Yêu cầu: Cho \(a_1,a_2,...,a_n\), hãy tìm lực lượng của tập \(DSET\) và số cách khác nhau để chọn tập \(DSET\).

Input

• Dòng đầu ghi hai số nguyên \(n\) và \(k\) (\(k \le 10^9\)).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1,a_2,...,a_n\) (\(a_i \le 10^9\)).

Output

• Gồm một dòng chứa hai số \(s,d\), trong đó \(s\) là lực lượng của tập \(DSET\), \(d\) là số cách khác nhau để chọn tập \(DSET\) chia dư cho \(k\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \le 20\).
• Subtask \(2\) (\(40\%\) số điểm): \(n \le 10^6\).
• Subtask \(3\) (\(10\%\) số điểm): \(n \le 10^9, a_i = i\) (khi đó file dữ liệu vào chỉ gồm một dòng chứa hai số nguyên \(n,k\)).

Example

2 100
1 2

1 2

Cho dãy số nguyên dương \(A_1,A_2,...,A_N\). Một bộ ba (\(i,j,k\)) được gọi là đẹp của dãy \(A\) đã cho nếu thỏa mãn:

• \(1 \le i \le j < k \le N\).
• Gọi dãy con liên tiếp \(A_i,A_{i+1},...,A_j\) là \(X\) và dãy con liên tiếp \(A_{j+1},A_{j+2},...,A_k\) là \(Y\) thì hai dãy này thỏa mãn:
  • Với mỗi giá trị xuất hiện trong dãy \(X\) thì cũng xuất hiện trong dãy \(Y\).
  • Với mỗi giá trị xuất hiện trong dãy \(Y\) thì cũng xuất hiện trong dãy \(X\).

Yêu cầu: Cho dãy số \(A\), hãy đếm số bộ ba đẹp (\(i,j,k\)) của dãy số này.

Input

• Dòng đầu chứa số nguyên \(N\) (\(1 \le N \le 2 \times 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(A_i\) (\(1 \le A_i \le N\)).

Output

• Ghi ra một số nguyên là số lượng bộ ba đẹp của dãy đã cho.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(N \le 500\).
• Subtask \(2\) (\(20\%\) số điểm): \(N \le 5000\).
• Subtask \(3\) (\(20\%\) số điểm): \(A_i \le 50\).
• Subtask \(4\) (\(20\%\) số điểm): mỗi giá trị xuất hiện đúng hai lần.
• Subtask \(5\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

7
3 1 2 1 2 3 1

4