Huy có một mảng ~A~ gồm ~10^{100}~ phần tử, ban đầu ~A_i = i~ với ~i~ nguyên dương. Lần lượt với từng ~A_i~, bắt đầu từ ~A_1~, Huy sẽ liên tục thực hiện các thao tác như sau:

• Nếu ~A_i~ chỉ có một chữ số thì Huy sẽ dừng lại và chuyển sang ~A_{i + 1}~ (nếu còn).
• Nếu không, Huy thay ~A_i~ thành tổng các chữ số của ~A_i~.

Ví dụ, sau khi hoàn thành các thao tác, ~A_{198}~ sẽ thành ~1 + 9 + 8 = 18~, sau đó lại đổi thành ~1 + 8 = 9~.

Sau khi hoàn thành, Huy sẽ có ~Q~ câu hỏi: Cho hai số nguyên dương ~L, R~, hãy tính tổng ~A_L + A_{L + 1} + \cdots + A_{R}~.

Input

• Dòng đầu tiên chứa một số nguyên dương ~Q~ ~(Q \le 100)~ là số câu hỏi.
• ~Q~ dòng sau, dòng thứ ~i~ chứa hai số nguyên dương ~L, R~ ~(1 \le L \le R \le 2^{60})~ là câu hỏi thứ ~i~.

Output

• In ra ~Q~ dòng, dòng thứ ~i~ chứa đáp án của câu hỏi thứ ~i~.

Sample Input

2
9 13
44 45

Sample Output

19
17

Giải thích: Trong câu hỏi thứ hai, ta có:

• ~A_{44} = 4 + 4 = 8~
• ~A_{45} = 4 + 5 = 9~.

Cho dãy ~a~ là một hoán vị của ~1, 2, \dots, n~. Ta gọi ~rmax(i, j) = max(a_i, a_{i + 1}, \dots, a_j)~ và ~rmin(i, j) = min(a_i, a_{i + 1}, \dots, a_j)~. Dựng một đồ thị vô hướng, trong đó hai đỉnh ~i, j~ ~(i \lt j)~ được nối với nhau nếu thỏa mãn một trong hai điều kiện sau:

• ~rmax(i, j) = a_i~ và ~rmin(i, j) = a_j~
• ~rmax(i, j) = a_j~ và ~rmin(i, j) = a_i~

Từ đồ thị đã cho vừa rồi, nhiệm vụ của bạn là tìm đường đi ngắn nhất từ đỉnh ~1~ đến đỉnh ~n~.

Input

Input gồm 2 dòng:

• Dòng đầu tiên chứa số nguyên dương ~n~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ là một hoán vị của ~1, 2, \dots, n~.

Output

• In ra một số nguyên duy nhất là độ dài đường đi ngắn nhất từ đỉnh ~1~ đến đỉnh ~n~.

Scoring

• Subtask 1 ~(60\%)~: ~n \le 2000~.
• Subtask 2 ~(40\%)~: ~n \le 3 \times 10^5~.

Sample Input

6
2 1 6 4 3 5 

Sample Output

4

Notes: Đồ thị dựng được từ dãy ~a~ trong test mẫu:

Khôi có một dãy ngoặc ~S~ độ dài ~N~, và cậu đang muốn đưa nó về dãy ngoặc đúng bằng cách thực hiện một số các thao tác như sau:

• Chọn ra hai số nguyên dương ~l, r~ ~(1 \le l \le r \le N)~, sau đó Khôi có thể sắp xếp lại các kí tự ở trong đoạn ~[l, r]~ theo thứ tự bất kì. Thời gian để thực hiện thao tác này là ~r - l + 1~ giây.

Hãy tìm xem Khôi sẽ mất ít nhất là bao nhiêu giây để đưa dãy ngoặc ban đầu về dãy ngoặc đúng, bằng cách sử dụng các thao tác như trên?

Input

• Dòng đầu gồm một số nguyên dương ~N~ ~(1 \le N \le 10^6)~.
• Dòng sau chứa dãy ngoặc ~S~ gồm có ~N~ kí tự.

Output

In ra trên một dòng một số nguyên duy nhất là thời gian tối thiểu để đưa dãy ngoặc ban đầu về dãy ngoặc đúng. Nếu không có cách nào để đưa về dãy ngoặc đúng thì in ra -1.

Subtasks

• Subtask 1 ~(20\%)~: ~N \le 10~.
• Subtask 2 ~(25\%)~: ~N \le 300~.
• Subtask 3 ~(25\%)~: ~N \le 3000~.
• Subtask 4 ~(30\%)~: Không có giới hạn gì thêm.

Sample Input

8
))((())(

Sample Output

6

Và em lại trang trí căn nhà của chúng ta

Và em đi trang trí những xanh tươi cành lá

Và em lại trang trí cây thông chờ Giáng Sinh

Và em đi trang trí những thói quen của mình

Để trang trí cho cây thông Noel năm nay, Hùng đã mua một dây đèn hình tròn rất dài. Dây đèn đó gồm ~N~ bóng đèn, bóng đèn thứ ~i~ xếp ngay cạnh bóng đèn thứ ~i + 1~ với ~i < N~ và bóng đèn ~N~ được xếp ngay cạnh với bóng đèn ~1~. Mỗi bóng đèn có thể tỏa sáng bằng ~M~ màu khác nhau, được đánh số từ ~1~ đến ~M~.

Để trang trí, Hùng sẽ gán cho mỗi bóng đèn một màu tương ứng, và theo cậu, sẽ khá nhàm chán nếu hai bóng đèn cạnh nhau có màu giống hệt nhau, và cậu sẽ không bao giờ làm vậy. Hãy đếm số cách mà Hùng có thể trang trí cho cây thông của mình. Hai cách trang trí là khác nhau nếu tồn tại ít nhất một bóng đèn mà được gán khác màu ở trong hai cách này.

Input

• Gồm một dòng duy nhất chưa hai số nguyên dương ~N, M~ ~(2 \le N, M \le 10^9)~.

Output

• In ra số cách trang trí thỏa mãn, chia lấy dư cho ~998244353~.

Subtasks

• Subtask 1 (~15\%~ số điểm): ~N, M \le 7~.
• Subtask 2 (~25\%~ số điểm): ~N, M \le 200~.
• Subtask 3 (~20\%~ số điểm): ~N, M \le 2000~.
• Subtask 4 (~30\%~ số điểm): ~N \le 10^6~.
• Subtask 5 (~10\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

3 3

Sample Output 1

6

Giải thích: Các cách trang trí hợp lệ là:

• ~(1, 2, 3)~
• ~(1, 3, 2)~
• ~(2, 1, 3)~
• ~(2, 3, 1)~
• ~(3, 1, 2)~
• ~(3, 2, 1)~

Sample Input 2

4 3

Sample Output 2

18