Nguồn đề : https://www.spoj.com/problems/ADACLEAN/

Cho một chuỗi kí tự s, có độ dài n, và một số nguyên k, hãy tính xem có bao nhiêu chuỗi con phân biệt có độ dài đúng bằng k của chuỗi s.

Chuỗi con của s là một chuỗi kí tự gồm các kí tự liên tiếp trong s.

Input

Dòng 1: t - số lượng test.

Dòng 2: n, k ~(1 ≤ n, k ≤ 10^5).~

Dòng 3: chuỗi kí tự s, bao gồm các chữ cái thường ('a'->'z').

Tổng n của tất cả các test không vượt quá ~10^6~

Kết quả

Với mỗi test in ra số lượng chuỗi kí tự con phân biệt có độ dài đúng bằng k .

Sample Input

5
3 2
aaa
5 1
abcba
4 2
abac
10 2
abbaaaabba
7 3
dogodog

Sample Output

1
3
3
4
4

Hexakill

Sau khi chơi chế độ Hexakill xong thì với bản năng của một dân competitive programming, Chuối hỏi rằng làm toán ở hệ cơ số khác thì như thế nào. Chuối giao cho bạn hai số ở hệ cơ số B( B = 16) là X, Y và nhờ bạn giúp Chuối làm những phép toán sau: 1. Tính tích các số từ X đến Y kể cả X và Y. 2. Tính S = tổng các chữ số trong kết quả nhận được. 3. Chừng nào S chưa nhỏ hơn B thì thực hiện lại việc tính tổng các chữ số của S. 4. Đưa ra S.

Input

• Dòng 1 chứa X
• Dòng 2 chứa Y
• X và Y chỉ chứa các kí tự từ '0'-'9', 'a'-'f' và 'A'-'F', ~( 1 \leq len(X), len(Y) \leq 10^{5} )~

Kết quả

• Đưa ra kết quả, nếu kết quả lớn hơn 9 đưa ra dưới dạng ký tự hoa.

Test

• 40d : ~( 1 \leq len(X), len(y) \leq 100 )~
• 60d : ~( 1 \leq len(X), len(y) \leq 10^{5} )~

Sample input 1

1Ba
1Bd

Sample output 1

F

Tuấn Anh là một người đam mê ngoại ngữ và anh ấy vừa xây dựng thành công một cỗ máy Suffix Three nhận biết ngôn ngữ hoạt động như sau, khi nhập vào một xâu kí tự thì cỗ máy sẽ phát hiện xâu kí tự đó là ngôn ngữ của nước nào theo quy tắc như sau :

• Nếu xâu kết thúc bằng "po" thì xâu đó là ngôn ngữ Filipino.
• Nếu xâu kết thúc bằng "desu" hoặc "masu" thì xâu đó là ngôn ngữ Japanese.
• Nếu xâu kết thúc bằng "mnida" thì xâu đó là ngôn ngữ Korean

Bạn hãy viết chương trình mô phỏng lại cỗ máy đó !

Input

Dòng đầu tiên gồm 1 số nguyên t ~(1 \le T \le 30)~, số lượng xâu bạn cần xử lí.

T dòng tiếp theo, mỗi dòng gồm một xâu S ~(1 \le |S| \le 10^5)~

Output

Với mỗi xâu S hãy in ra ngôn ngữ của xâu đó.

Bộ test đảm bảo rằng tất cả các xâu chỉ có kết thúc bằng "po", "desu", "masu" hoặc "mnida".

Sample Input

8
kamusta_po
genki_desu
ohayou_gozaimasu
annyeong_hashimnida
hajime_no_ippo  
bensamu_no_sentou_houhou_ga_okama_kenpo
ang_halaman_doon_ay_sarisari_singkamasu 
si_roy_mustang_ay_namamasu

Sample Output

FILIPINO
JAPANESE
JAPANESE
KOREAN
FILIPINO
FILIPINO
JAPANESE
JAPANESE

Nguồn đề : codeforces

update problem's source after contest : https://codeforces.com/contest/1133/problem/A

setter's soluion : https://codeforces.com/contest/1133/submission/110623261

Tuấn Anh là một học sinh tài năng của khóa 18 FITHOU, với thành tích học tập đáng nể kì nào anh cũng được học bổng loại giỏi, nên anh ta trở nên nổi tiếng toàn trường. Vì là sinh viên giỏi, nên anh rất được các bạn nữ ái mộ. Một hôm, có một bạn nữ hỏi anh: "Thời gian tự học của Tuấn Anh - kun bắt đầu và kết thúc khi nào?", Tuấn Anh nói anh ấy học từ h1 : m1 đến h2 : m2 và quy định của anh ấy là: thời gian học kéo dài theo số phút chẵn, toàn bộ thời gian học chỉ được trong 1 ngày để đảm bảo sức khỏe và tối thiểu thời gian học phải kéo dài ít nhất 2 phút (người học giỏi thật là có những quy định thật kì lạ).

Sau khi các bạn nữ đã thỏa mãn với câu trả lời của Tuấn Anh, anh ấy lại tiếp tục suy nghĩ với câu trả lời của mình, anh ta nhận ra mình dễ dàng tìm ra mốc thời gian chính giữa của khoảng thời gian mình đã học. Điều này khá dễ dàng với Tuấn Anh, nên Tuấn Anh đã đem bài tập này dành cho Hải (là học sinh cá biệt của lớp), các bạn hãy giúp Hải giải quyết bài toán này để Hải không bị Tuấn Anh chửi nào ^^

Ví dụ: Nếu Tuấn Anh học từ 10:00 đến 14:00 thì mốc thời gian chính giữa là 12:00

Input

Dòng đầu chứa 2 số nguyên h1 và m1 theo định dạng hh:mm

Dòng đầu chứa 2 số nguyên h2 và m2 và cũng theo theo định dạng hh:mm

Điều kiện: 0 <= h1, h2 <= 23 và 0 <= m1, m2 <= 59

Và 2 mốc thời gian phải đảm bảo quy định của Tuấn Anh (như trên)

Output

In ra 2 số h3 và m3 (0 <= h3 <= 23, 0 <= m3 <= 59) tương đương với mốc giữa của thời gian Tuấn Anh học theo định dạng hh:mm. In mỗi số chính xác 2 chữ số (có thể thêm tiền tố 0 nếu cần), ngăn cách chúng với ':'

Input 01

10:00

11:00

output 01

10:30

Input 02

11:10

11:12

output 02

11:11

Sau khi bị ThangPhan bủh bủh lmao cho mấy phát, Mạnh Đạt quá cay cú nên quyết định học thuật dảk wa' no jutsu để quyết đấu với ThangPhan. Để học được nhẫn thuật, Mạnh Đạt phải làm theo hướng dẫn của quyển "How to become dảk". Theo hướng dẫn, Mạnh Đạt được cho 1 số n và 1 số k. Quyển sách bao gồm tất cả các chuỗi có độ dài là n, mỗi chuỗi bao gồm 2 ký tự 'b' và n - 2 ký tự 'a'. được sắp xếp theo thứ tự từ điển.
Ví dụ, n = 5 thì các chuỗi lần lượt là :

1. aaabb
2. aabab
3. aabba
4. abaab
5. ababa
6. abbaa
7. baaab
8. baaba
9. babaa
10. bbaaa

Cũng không dễ dàng nhận thấy lắm nhưng ThangPhan bảo dễ dàng là quyển sách sẽ chứa n * (n-1) / 2 chuỗi. Biết n và k, hãy giúp Mạnh đạt tìm ra chuỗi thứ k trong quyển sách trên giúp Mạnh Đạt trở nên dảk để đánh bại ThangPhan.

INPUT : Dòng đầu tiên chứa 1 số t (1 <= t <= 10000) - số lượng testcases. Tiếp theo là t dòng, mỗi dòng chứa n và k. (3 <= n <= 10005, 1 <= k <= min(2 * 10^9, n * (n-1) / 2).

OUTPUT : Ứng với mỗi test case là 1 chuỗi thứ k tương ứng.

EXAMPLE :
input :
7
5 1
5 2
5 8
5 10
3 1
3 2
20 100

output :

aaabb
aabab
baaba
bbaaa
abb
bab
aaaaabaaaaabaaaaaaaa