Vào năm 2256, khi trình độ khoa học và kĩ thuật đã đạt đến 1 ngưỡng nhất định, con người đã bắt đầu khám phá vũ trụ rộng lớn. Trong vòng 100 năm sau đó, họ đã đến được vô số các hành tinh và gặp rất nhiều giống loài mới. Khi các giống loài có thể hiểu được ngôn ngữ của nhau thông qua máy dịch ngôn ngữ, họ đã cùng nhau tạo nên United Federation of Planets (Liên hiệp các Hành tinh). Đó là nơi để tập hợp, chia sẻ và đoàn kết với nhau để ai cũng có thể biến ước mơ du hành khắp các vì sao trở thành hiện thực.

Michael Burnham là một người được Đại sứ* Sarek, cha đẻ của Spock, nuôi dưỡng trên *Vulcan. Khi cô bị Nhóm thám hiểm Vulcan từ chối vì nhân tính của mình, Sarek đã gửi Burnham đến* Starfleet* nơi cô phục vụ trên USS Shenzhou trong bảy năm dưới quyền của Đại úy Phillipa Georgiou. (Starfleet : là lực lượng không gian được Liên đoàn các hành tinh thống nhất duy trì làm phương tiện chính để tiến hành khám phá không gian sâu, nghiên cứu, quốc phòng, gìn giữ hòa bình và ngoại giao)

Sự trỗi dậy khủng khiếp của Burnham để trở thành sĩ quan đầu tiên của Thần Châu đã đi đến kết cục bi thảm khi cô bật đội trưởng của mình với hy vọng ngăn chặn một cuộc chiến với Đế chế* Klingon đang hồi sinh. Thay vào đó, chiến tranh bắt đầu và cuộc xung đột ban đầu, được đặt tên là *Trận chiến sao đôi, đã cướp đi sinh mạng của Đại úy* Georgiou* và chứng kiến sự hủy diệt của Thần Châu. Burnham bị kết án chung thân vì tội nổi loạn tại một thuộc địa hình sự của Liên bang.

Sau 6 tháng bóc lịch, Burnham *hiện có cơ hội chuộc lỗi bằng cách phục vụ như Chuyên gia Khoa học của tàu *USS Discovery số hiệu NCC-1031. Mặc dù cô đã có một vài người bạn - bạn cùng phòng Cadet Sylvia Tilly *coi Burnham là người cố vấn của cô - và cô được Đại úy *Gabriel Lorca đánh giá cao nhưng Burnham phải vật lộn với cuộc sống trên tàu một lần nữa bởi những sai lầm của cô.

Ngày sao thứ 141, phát hiện có vài tín hiệu lạ ở một số hành tinh nhất định, với tư cách là Chuyên gia Khoa học, Burnham được giao nhiệm vụ phải quét tất các các hành tinh có trên bản đồ. Cô dự định sẽ thả các phi thuyền không người lái để quét các hành tinh xung quanh tìm tín hiệu trong hệ sao đó, nhưng có lẽ khoảng cách giữa các hệ sao với nhau quá xa để phi thuyền không người lái có thể tiếp cận. May thay vũ khí lớn nhất của Discovery là mạng dịch chuyển bào tử sợi nấm, nó giúp con tàu di chuyển giữa các hệ sao chỉ trong nháy mắt. Cô tự hỏi con tàu Discovery phải* nhảy* bao nhiêu lần qua hệ sao khác để quét được hết tất các hành tinh. Các bạn hãy giúp cô ấy nhé!

Yêu cầu:

* Một hệ sao* là tập hợp các hành tinh được liên kết vô hướng với nhau sao cho từ một hành tinh bất kì, ta luôn có thể đến tất cả các hành tinh khác trong cùng một hệ sao bằng cách đi qua một số liên kết vô hướng có trong hệ.

• Cho một bản đồ gồm ~n~ hành tinh và ~m~ liên kết vô hướng giữa hai hành tinh. Phi thuyền có thể xuất phát từ một hành tinh bất kì. Hãy đếm số bước* nhảy* ít nhất cần thực hiện để đi qua tất cả các hệ sao.

Input:

• Dòng đầu tiên chứa hai số nguyên n, m là số hành tinh và số liên kết có trong bản đồ.

• m dòng tiếp theo, mỗi dòng gồm hai số nguyên u, v mô tả có một liên kết vô hướng giữa hành tinh u và hành tinh v

Output: Một số nguyên duy nhất là số bước nhảy ít nhất cần thực hiện để đi qua tất cả các hệ sao

Giới hạn: ~1 ≤ n ≤ 10^5~, ~1 ≤ m ≤ 2.10^5~

INPUT

4 2
1 2
3 4

OUTPUT

1

*Giải thích: *

Tàu bắt đầu từ hành tinh 3 thì sẽ quét được hành tinh 3, 4

Sau đó phải thực hiện một lần "nhảy" để đến được hành tinh 2, từ đó có thể quét được hành tinh 1, 2

Sau khi tìm ra được các tín hiệu, nhận lệnh từ cấp trên, chỉ huy Gabriel Lorca của tàu USS Discovery muốn đưa tàu đến đó để tìm hiểu thêm về các tín hiệu. Sự di chuyển trong mạng lưới bào tử sợi nấm được đảm nhiệm bởi 1 thứ gọi là Động cơ bào tử, động cơ bào tử cần sử dụng trung gian là 1 con Tardigrade để làm hoa tiêu dẫn đường trong mạng lưới sợi nấm.

Nhưng năng lượng tác động lên sinh vật đó sau mỗi lần nhảy quá lớn nên chỉ trong vài lần sau đó, con Tardigrade duy nhất đã rơi vào trạng thái ẩn sinh tột độ bằng cách giảm lượng nước trong cơ thể xuống dưới 1%. Đang trong thời chiến và loài Tardigrade cũng đang trong nguy cơ tuyệt chủng, họ không thể làm gì khác ngoài việc cố gắng hồi sức cho nó. Trong tình thế gấp gáp, 1 ý tưởng táo bạo nhưng không kém phần xuất sắc đó là hợp nhất DNA của Tardigrade vào cơ thể trung úy Paul Stamets (là người khám phá ra động cơ bào từ). Dù thử nghiệm thành công nhưng với số hành tinh cần kiểm tra quá lớn dẫn đến số lần nhảy có thể rất nhiều. Paul Stamets muốn biết được ngưỡng năng lượng lớn nhất qua hàng loạt các cú nhảy để có biện pháp phòng ngừa kịp thời. Năng lượng qua các lần nhảy sẽ biến động tuần hoàn theo chu kì mà trung úy Paul sẽ cung cấp cho các bạn ngay bên dưới. Các bạn hãy giúp anh ấy nhé!

-Yêu cầu

Các hành tinh được xem như 1 dãy số. Năng lượng cần để nhảy đến hành tinh ~i~ là ~a[i]~. Paul sẽ thực hiện 1 số lần nhảy bất kì ~(\geq1)~ và năng lượng qua các lần nhảy như sau: VD: số lần nhảy là ~k~ ~(i_1 < i_2 < … < i_k)~ thì năng lượng tổng: ~3 \cdot a[i_1] + 1 \cdot a[i_2] - 4 \cdot a[i_3] + 3 \cdot a[i_4] + 1 \cdot a[i_5] - 4 \cdot a[i_6] + ….. a[i_k]~

Tìm năng lượng tổng lớn nhất

INPUT

Dòng đầu tiên chứa ~T~ là số testcase ~(T \leq 10)~

+~T~ nhóm, mỗi nhóm có dạng:

+~N~ là số hành tinh ~(N \leq 10^5)~

+Tiếp theo là ~N~ số ~a[i]~ ~(-10^5 \leq a[i] \leq 10^5)~ biểu thị năng lượng khi nhảy đến hành tinh ~i~

OUTPUT

In ra ~T~ dòng, mỗi dòng là kết quả của testcase đó

Sample input 1

1
5
-7 -9 -2 8 2

Sample output 1

26

Sample input 2

1
2
-4 -3

Sample output 2

-9

*Giải thích test 1: Paul sẽ chọn ~i = 4~ và ~i = 5~, khi đó năng lượng sẽ là ~3 \cdot 8 + 1 \cdot 2 = 26~

Có thế thấy không có cách chọn nào để năng lượng lớn hơn

*Tính điểm: *

Subtask 1: ~T = 1, n \leq 20~ (25%)

Subtask 2: ~T = 10, n \leq 10^3~ (50%)

Subtask 3: Không có ràng buộc gì thêm (25%)

Ôi không!! Sau hàng loạt các cú nhảy qua các hành tinh, mặc dù đã lường trước sự nguy hiểm khi thay thế Tardigrade làm hoa tiêu dẫn đường trong mạng lưới sợi nấm, nhưng lượng năng lượng truyền vào cơ thể quá lớn đã làm trung úy Paul Stamets bất tỉnh. Khi anh tỉnh lại, biết được nhiệm vụ đã hoàn thành, anh rất vui sung sướng vì đã làm được điều từ trước nay chưa bao giờ xảy ra.

Đã đến lúc về nhà rồi. Bây giờ Paul sẽ thực hiện thêm cú nhảy cuối cùng để về nhà. Nhưng…mọi người trên tàu không hay biết cú nhảy cuối cùng này sẽ làm cho sức chịu đựng của Paul vượt quá giới hạn. Bùmm …. Con tàu đã nằm ở tọa độ của trụ sở của Liên Hiệp, nhưng ở đó chẳng có gì cả. Sau vài phút hoang mang, họ đã nhận ra họ đang ở tọa độ chính xác nhưng là tọa độ của 1 vũ trụ song song!!

Ở vũ trụ song song này, cũng tồn tại một liên hiệp nhưng là một liên hiệp để chống lại đế chế Terran do con người lãnh đạo. Để hòa nhập vào vũ trụ này, con tàu Discovery bắt buộc phải thay đổi để không bị nhận ra và tiêu diệt bởi con người. Vì con tàu rất lớn và có rất nhiều chi tiết tinh xảo, tỉ mỉ nên không dễ dàng gì để thay đổi trong tức khắc. Các bạn hãy giúp các robot tìm những điểm giống nhau để bỏ qua và tăng tốc độ sửa chữa nhé.

Yêu cầu:

Xem các chi tiết của con tàu là xâu ~A~ độ dài ~N~, các thông tin thu thập được ở vũ trụ này là ~M~ xâu ~B[i]~. Tìm số lượng xâu con không liên tiếp trong ~A~ giống với ít nhất 1 xâu ~B[i]~.

Trong trường hợp bạn quên mất, xâu ~X~ là xâu con không liên tiếp của ~Y~ khi và chỉ khi tồn tại một cách xóa đi một hoặc một số ký tự của xâu ~Y~ sao cho tạo được xâu ~X~.

INPUT

• Dòng đầu tiên gồm 2 số nguyên dương ~N~ và ~M~ ~(N, M \leq 10^5)~lần lượt là số lượng ký tự của xâu ~A~ và số lượng xâu ~B~.
• Dòng tiếp theo là xâu ~A~, xâu ~A~ đảm bảo chỉ gồm các ký tự chữ cái thường và không có dấu cách.
• ~M~ dòng tiếp theo lần lượt là các xâu ~B[i]~, các xâu đều có đúng 3 chữ cái thường và các xâu là phân biệt.

OUTPUT

• Một số nguyên duy nhất là số lượng xâu con không liên tiếp trong ~A~ giống với ít nhất 1 xâu ~B[i]~.

Sample input

12 2
lhbhdmamndln
ldn
hmd

Sample output

7

Giải thích

Tính điểm:

• 25% số test thỏa ~N \leq 50, M \leq 300~
• 25% số test thỏa ~N \leq 500~
• 25% số test thỏa ~M = 1~
• 25% số test không ràng buộc gì thêm

Ở vũ trụ song song này, người đứng đầu Terran lại là 1 bản sao của Đại úy Phillipa Georgiou (đã nhắc đến ở trên), dẫn dắt cả đội quân hùng mạnh giết chóc và cướp bóc khắp mọi nơi. Phillipa cùng đội quân của bà ta có 1 trụ sở gọi là Cung điện bay, nó to gấp nghìn lần những tàu vũ trụ khác và sử dụng tận gốc năng lượng bào tử để duy trì hoạt động, chế tạo vũ khí và gây ảnh hưởng đến mạng lưới sợi nấm trên đa vũ trụ.

Ở thế giới này, Michael Burnham là cánh tay phải của bà ta, lợi dụng điều đó* Michael* đã tìm cách len lỏi vào để lật đổ đế chế Terran, mang lại hòa bình cho vũ trụ này và làm sạch mạng lưới sợi nấm. Vậy nhưng, trong lúc ấy cô vô tình phát hiện ra hạm trưởng của mình Gabriel Lorca(đã nhắc đến ở trên) là Terran-er, ông đã từng nuôi hy vọng đạp đổ Phillipa và chiếm lĩnh đế chế Terran nhưng không thành công. Bằng một cách nào đó ông ta lại bị rơi vào thế giới kia, ông muốn lợi dụng động cơ bào tử để quay trở lại thế giới của mình và tiếp tục kế hoạch thống trị.

Các đồng đội trên tàu của Michael đã hỗ trợ rất tốt cho cô ấy bằng cách lên kế hoạch đặt boom để phá hủy* cung điện bay*. Về phía Michael, cũng là một người khá trọng nghĩa, khi quả boom gần phát nổ, cô đã chớp lấy thời cơ để đưa Phillipa dịch chuyển về USS Discovery. Đã gần như tiêu diệt hoàn toàn được đế chế Terran, việc bây giờ là đưa Discovery trở về đúng vũ trụ của nó, và cũng là nơi xuất phát của Michael và những người khác.

Khi Michael dẫn theo Phillipa về, trung úy Paul đã tìm lại được tọa độ ở vũ trụ cũ trước khi lạc sang thế giới này. Và .... nhảy. Anh ấy cứ rẽ trái, rẽ phải, rồi lại rẽ trái. Lần này con đường trong mạng lưới sợi nấm dường như dài hơn rất nhiều, dù biết trước tọa độ ở các ngã rẽ sẽ có dạng ~dx[i] = dx[i-1] + dx[i-2]~ nhưng anh không lường trước việc con đường về nhà lại xa đến vậy. Các bạn hãy giúp anh ấy cùng phi hành đoàn về đến quê hương của mình nhé.

Yêu cầu

Cho ~L, R (L \leq R)~, hãy tính tổng các chữ số cuối cùng của các ~dx[i]~ với ~L \leq i \leq R~. Bởi vì tổng này có thể rất lớn nên bạn chỉ cần in ra chữ số cuối cùng của nó.

Biết ~dx[1] = dx[2] = 1~

Input:

Dòng đầu tiên là ~T~, biểu thị số test.

Mỗi test gồm ~2~ số ~L~ và ~R~.

Output:

Gồm ~T~ dòng in ra chữ số cuối của tổng các chữ số cuối cùng của ~dx[i]~ với ~L <= i <= R~.

Tính điểm:

Subtasks: Mỗi subtask chiếm ~25~% số test.

Subtask 1: ~T ≤ 10;~ ~l, r \leq 10^6~

Subtask 2: ~T ≤ 10~^~4~~; l = r ≤ 10~^~18~

Subtask 3: ~T ≤ 10~^~4~~; l = 1, r ≤ 10~^~18~

Subtask 4: ~T ≤ 10~^~4~~;~ ~l~ ~,~ ~r ≤ 10~^~18~

Ví dụ:

Input 1

3
1 5
2 4
3 6

Output 1

2
6
8

Input 2

2
2 10
4 4

Output 2

2
3

Giải thích

10 ~dx[i]~ đầu tiên là ~1, 1, 2, 3, 5, 8, 13, 21, 34, 55~

Note: Nếu bạn thấy quá khó khăn, vì thuong_chirox9 là một người đáng iu (không phải như HMD) nên đã cho bạn một số gợi ý .

Khi phi hành đoàn đã trở về quê hương an toàn, vì đã hoàn thành nhiệm vụ một cách xuất sắc, Michael Burnham được tặng thưởng một cỗ máy thời gian tân tiến nhất và một ngày nghỉ. Michael quyết định dùng ngày nghỉ ấy để đến các thời điểm khác nhau nghỉ dưỡng. Khi đã tỉnh táo sau một đêm quẩy bar với đồng đội, Michael lên cỗ máy và nhảy đến một năm ngẫu nhiên. Nhưng số cô còn xui hơn con rệp, cô đã nhảy vào giữa Thế chiến II và suýt thì ngủm vì bom hạt nhân.

Vì đã quá chán ngán với những cuộc chiến và không thể tin vào vận may của mình thêm nữa, Michael đã tìm đến Chirox để hỏi xem nên nhảy đến năm nào để có thể yên tâm nghỉ dưỡng. Chirox cũng chẳng biết gì, nhưng cô đã chỉ cho Michael một cách giảm rủi ro: theo nghiên cứu của Chirox, những năm dễ thương thường là những năm yên bình.

Năm dễ thương là năm có các chữ số đôi một phân biệt. Ví dụ năm ~2013~ là một năm dễ thương. Còn ~2020~ và ~2021~ thì không phải là năm dễ thương và bạn cũng biết chuyện gì đã xảy ra trong hai năm này rồi đấy.

Michael quyết định mù quáng nghe theo Chirox. Hiện* Michael* đang ở năm ~Y~ và cô muốn nhảy đến năm dễ thương ~C~ gần nhất. Và vì là một con người luôn tiến tới chứ không biết lùi là gì, Michael muốn năm ~C~ là tương lai của năm ~Y~.

Yêu cầu:

Cho năm ~Y~, hãy tìm năm ~C~ gần ~Y~ nhất sao cho ~C (C > Y)~ là một năm dễ thương.

Input: một số nguyên duy nhất là ~Y~ ~(Y ≤ 5000)~

Output: một số nguyên duy nhất là năm ~C~ cần tìm.

Ví dụ:

Input:

1989

Output:

2013

Giải thích: các năm ~1990, 1991, 1992, 1993,..., 2012~ đều không phải năm dễ thương vì có các chữ số trùng nhau. Năm ~2013~ là một năm dễ thương vì các chữ số đôi một phân biệt. Vậy ~2013~ là năm mà Michael muốn nhảy tới.