Trong tủ đồ chơi của một lớp học mẫu giáo có bộ đồ sắp chữ gồm các tấm bìa. Trên mỗi tấm bìa có đúng một ký tự la tinh thuộc ~n~ ký tự đầu tiên của bảng chữ cái (~a, b, c, \dots~). Có ~c_i~ tấm bìa ghi ký tự thứ ~i~ (tức ký tự ~a~ ứng với ~i=1~, ~b~ ứng với ~i=2~, …), với ~i = 1 \dots n~.

Cô giáo sắp tất cả các tấm bìa thành một dãy ngang (tạo thành một xâu). Một cặp tốt là một cặp hai tấm bìa đứng cạnh nhau (từ trái sang phải) sao cho ký tự trên tấm bên phải là ký tự kế tiếp trong bảng chữ cái của ký tự trên tấm bên trái. Ví dụ: xâu "abdc" có ~1~ cặp tốt (chỉ có "ab"), còn "abcdefghijklmnopqrstuvwxyz" có ~25~ cặp tốt.

Yêu cầu

Hãy xác định số lượng cặp tốt lớn nhất có thể đạt được khi sắp tất cả các tấm bìa thành một dãy.

Dữ liệu

• Dòng đầu chứa số nguyên ~n~ (~1 \le n \le 26~).
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên ~c_i~ (~1 \le c_i \le 10^9~).

Kết quả

In ra một số nguyên: số cặp tốt tối đa có thể nhận được.

Ví dụ

Ví dụ 1

Input

2
3
4

Output

3

Ví dụ 2

Input

3
1
1
1

Output

2

Ràng buộc

• ~1 \le n \le 26~
• ~1 \le c_i \le 10^9~

An được giao nhiệm vụ mua đủ ~n~ món đồ theo đúng thứ tự từ ~1~ đến ~n~. Món đồ thứ ~i~ có trọng lượng ~w_i~. Siêu thị cho miễn phí số lượng túi giống nhau không giới hạn, mỗi túi chịu được trọng lượng tối đa ~q~ (luôn có ~w_i \le q~).

An mua lần lượt từng món, và sau khi mua xong một món sẽ cố gắng cho vào một túi đang dùng có tổng khối lượng hiện tại lớn nhất sao cho sau khi thêm món đó vào thì túi vẫn không vượt quá ~q~. Nếu không có túi nào đang dùng có thể chứa thêm món mới, An sẽ dùng một túi mới cho món đó.

Lưu ý: Một món đồ đã cho vào túi thì không lấy ra để chuyển sang túi khác.

Yêu cầu

Với mỗi test, hãy tính số túi An sẽ sử dụng nếu mua ~n~ món đồ theo đúng quy tắc trên.

Dữ liệu

• Dòng ~1~ chứa số nguyên dương ~T~ (~T \le 10^4~) là số test.

• Mỗi test gồm:

  • Dòng ~1~ chứa hai số nguyên dương ~n, q~ (~n \le 2 \times 10^5~, ~q \le 10^9~).
  • Dòng ~2~ chứa ~n~ số nguyên dương ~w_1, w_2, \dots, w_n~ với mọi ~i~ đều có ~w_i \le q~.

Tổng các giá trị ~n~ qua tất cả các test không vượt quá ~2 \times 10^5~. Các số trên một dòng cách nhau bởi dấu cách.

Kết quả

Với mỗi test, in ra một số nguyên trên một dòng: số túi An sử dụng.

Ví dụ

Ví dụ 1

Input

3
6 14
8 4 6 1 7 2
8 9
8 7 6 5 4 3 2 1
9 9
5 5 5 2 3 4 4 4 4

Output

3
4
5

Giải thích

Ví dụ ~1~

Xét test ~1:~ ~n=6~, ~q=14~, dãy ~w=[8,4,6,1,7,2]~.

• Món ~1~ (~8~) vào túi ~1~ (túi ~1:~ ~8~)
• Món ~2~ (~4~) vào túi ~1~ (túi ~1:~ ~12~)
• Món ~3~ (~6~) không vào được túi ~1~ ⇒ tạo túi ~2~ (túi ~2:~ ~6~)
• Món ~4~ (~1~) vào túi nặng nhất có thể chứa: túi ~1~ (túi ~1:~ ~13~)
• Món ~5~ (~7~) vào túi ~2~ (túi ~2:~ ~13~)
• Món ~6~ (~2~) không vào được túi ~1~ hay túi ~2~ ⇒ tạo túi ~3~ (túi ~3:~ ~2~)

Vì vậy test ~1~ dùng ~3~ túi.

Ràng buộc và chấm điểm

Ràng buộc

• ~T \le 10^4~
• ~n \le 2 \times 10^5~
• ~q \le 10^9~
• ~w_i \le q~ với mọi ~i~
• Tổng ~n~ qua mọi test ~\le 2 \times 10^5~

Chấm điểm

• Subtask ~1~ ~(50\%):~ ~T \le 10~ và ~n \le 1000~
• Subtask ~2~ ~(50\%):~ Không có ràng buộc bổ sung.

Một tập hợp ~A={a_1,a_2,\dots,a_k}~ gồm ~k~ số tự nhiên khác nhau, có tổng các phần tử bằng ~n~, được gọi là tập sinh chính phương nếu tổng của bất kỳ ~k-1~ phần tử trong ~A~ đều là một số chính phương (tức tồn tại số nguyên ~t~ sao cho tổng đó bằng ~t^2~).

Ví dụ: ~A={9,34,57,78}~, ~k=4~, ~n=178~ là một tập sinh chính phương vì:

• ~9+34+57=100=10^2~
• ~9+34+78=121=11^2~
• ~9+57+78=144=12^2~
• ~34+57+78=169=13^2~

Yêu cầu

Cho hai số nguyên ~n~ và ~k~, hãy xây dựng một tập ~A~ gồm ~k~ số tự nhiên khác nhau, có tổng bằng ~n~ và là tập sinh chính phương như định nghĩa trên; hoặc cho biết rằng không tồn tại tập hợp như vậy.

Dữ liệu

Một dòng chứa hai số nguyên ~n~ và ~k~ với ~2 \le n \le 200000~, ~2 \le k \le 30~.

Kết quả

• Nếu tồn tại tập ~A~ thỏa mãn:

  • Dòng 1 in YES
  • Dòng 2 in ra ~k~ số tự nhiên (các phần tử của tập ~A~) cách nhau bởi dấu cách. Nếu có nhiều đáp án, in ra bất kỳ.
• Nếu không tồn tại, in NO.

Ví dụ

Ví dụ 1

Input

178 4

Output

YES
9 34 57 78

Ràng buộc và chấm điểm

Ràng buộc

• ~2 \le n \le 200000~
• ~2 \le k \le 30~

Chấm điểm

• Subtask ~1~ ~(30\%):~ ~k=2~
• Subtask ~2~ ~(30\%):~ ~k=3~
• Subtask ~3~ ~(40\%):~ Không có ràng buộc bổ sung ngoài các ràng buộc đã nêu.

Tom đang làm việc cho một công ty mạng. Dữ liệu của công ty được mã hoá thành các số nguyên và lưu trong mảng gồm ~N~ phần tử ~A_1, A_2, \dots, A_N~. Công ty lo ngại rằng nếu trong một đoạn dữ liệu có hai giá trị trùng nhau thì có thể gây loạn thông tin.

Công ty đưa ra ~Q~ truy vấn, mỗi truy vấn yêu cầu kiểm tra một đoạn con của mảng có tồn tại ít nhất hai phần tử bằng nhau hay không.

Yêu cầu

Với mỗi truy vấn ~[u_i, v_i]~, hãy xác định xem trong dãy ~A_{u_i}, A_{u_i+1}, \dots, A_{v_i}~ có tồn tại hai chỉ số ~p < q~ sao cho ~A_p = A_q~ hay không.

• Nếu có, in ra ~1~.
• Nếu không, in ra ~0~.

Dữ liệu

• Dòng 1: hai số nguyên ~N~ và ~Q~.
• Dòng 2: ~N~ số nguyên ~A_1, A_2, \dots, A_N~ ( ~1 \le A_i \le 10^9~ ).
• ~Q~ dòng tiếp theo: mỗi dòng gồm hai số nguyên ~u_i~ và ~v_i~ ( ~1 \le u_i \le v_i \le N~ ) là đoạn cần kiểm tra.

Kết quả

In ra ~Q~ chữ số liên tiếp (theo đúng thứ tự truy vấn). Với mỗi truy vấn, in ~1~ nếu đoạn đang xét có hai số trùng nhau, ngược lại in ~0~.

Ví dụ

Ví dụ 1

Input

3 4
1 2 2
1 1
1 2
1 3
2 3

Output

0011

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le A_i \le 10^9~.
• ~1 \le u_i \le v_i \le N~

Chấm điểm

• Có ~30\%~ số test ứng với ~30\%~ số điểm có ~1 \le N,Q \le 10^3~
• Có ~30\%~ số test ứng với ~30\%~ số điểm có ~1 \le N,Q \le 10^5~
• Có ~40\%~ số test ứng với ~40\%~ số điểm có ~1 \le N,Q \le 10^6~

Kỷ Devon bắt đầu từ ~419.2~ triệu năm trước và kết thúc vào ~358.9~ triệu năm trước. Dựa trên các hóa thạch tìm được, các nhà khảo cổ học xây dựng một dãy số nguyên dương ~e_1, e_2, e_3, \dots~ thể hiện đặc trưng tiến hóa của sinh vật trong kỷ này.

Dãy được tạo theo quy tắc: với mọi ~i>1~, số ~e_i~ nhận được từ ~e_{i-1}~ bằng cách tăng đúng một chữ số (trong biểu diễn thập phân) lên 1 đơn vị. Tương đương, tồn tại ~k \ge 0~ sao cho ~e_i = e_{i-1} + 10^k~ (với điều kiện chữ số ở hàng ~10^k~ của ~e_{i-1}~ không phải ~9~ để việc tăng một chữ số là hợp lệ).

Các hóa thạch cho phép xác định ~n~ số đặc trưng ~a_1, a_2, \dots, a_n~ thỏa ~a_i < a_{i+1}~.

Yêu cầu

Hãy tìm một dãy ~e_1, e_2, \dots, e_m~ sao cho:

• ~e_1 = a_1~
• Dãy ~e~ chứa ~n~ số đã biết theo đúng thứ tự, tức tồn tại các chỉ số ~1 = p_1 < p_2 < \dots < p_n \le m~ sao cho ~e_{p_j} = a_j~
• Mỗi bước chuyển thỏa ~e_i = e_{i-1} + 10^k~ với một ~k \ge 0~ (tăng đúng một chữ số lên 1).

Trong tất cả các dãy thỏa mãn, chọn dãy có tổng ~e_1 + e_2 + \dots + e_m~ nhỏ nhất. Hãy xuất ra tổng nhỏ nhất đó theo mô đun ~10^9+7~.

Dữ liệu

• Dòng đầu chứa số nguyên ~n~ (~1 \le n \le 10^3~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~, thỏa ~a_i < a_{i+1}~. Mỗi ~a_i~ có không quá ~10^3~ chữ số.

Kết quả

Ghi ra một số nguyên: tổng nhỏ nhất tìm được theo mô đun ~10^9+7~.

Ví dụ

Ví dụ 1

Input

3
1 2 43

Output

118

Ràng buộc

• ~1 \le n \le 10^3~
• ~a_i~ là số nguyên dương, mỗi số có không quá ~10^3~ chữ số
• ~a_i < a_{i+1}~ với mọi ~i = 1 \dots n-1~