Thầy Quýt kể: số 7 là số áo huyền thoại của bóng đá thế giới. Ban tổ chức giải đấu mini của lớp quyết định tặng huy hiệu cho những bạn có số áo "huyền thoại" — tức là số áo có chứa chữ số 7 (ví dụ 7, 17, 71, 707). Các số áo được đánh liên tiếp từ a đến b. Hỏi có bao nhiêu bạn được nhận huy hiệu?

Input: Một dòng chứa hai số nguyên a và b.

Output: Số lượng số trong đoạn ~[a, b]~ có chứa chữ số 7.

Ràng buộc: ~1 ≤ a ≤ b ≤ 10^6~

Ví dụ:

Input:

1 20

Output:

2

Giải thích: trong đoạn ~[1, 20]~ có hai số chứa chữ số 7 là 7 và 17.

Bình luận viên nhận xét: điều đáng sợ nhất ở một đội bóng World Cup là "phong độ" — chuỗi trận liên tiếp không thua. Thầy Quýt tra lại n trận gần nhất của đội tuyển mình yêu thích, mỗi trận có kết quả: 2 nghĩa là thắng, 1 nghĩa là hòa, 0 nghĩa là thua. Hãy tìm chuỗi trận liên tiếp không thua (chỉ gồm thắng hoặc hòa) dài nhất của đội.

Input: Dòng đầu là số nguyên n. Dòng sau gồm n số nguyên, mỗi số là kết quả một trận theo thứ tự thời gian.

Output: Độ dài của chuỗi trận liên tiếp không thua dài nhất.

Ràng buộc: ~1 ≤ n ≤ 10^5~. Kết quả mỗi trận chỉ nhận giá trị 0, 1 hoặc 2.

Ví dụ:

Input:

8
2 1 0 2 2 1 0 2

Output:

3

Giải thích: chuỗi không thua dài nhất là ba trận liên tiếp thắng–thắng–hòa (~2, 2, 1~) ở giữa dãy.

Sân vận động nơi thầy Quýt xem World Cup 2026 có n khu khán đài đánh số từ 1 đến n theo vòng tròn. Khán giả chơi trò "làn sóng người": sóng bắt đầu từ khu s, mỗi giây lan sang khu kế tiếp (từ khu n sẽ quay lại khu 1). Hỏi sau k giây, làn sóng đang ở khu nào?

Input: Một dòng chứa ba số nguyên n, s, k.

Output: Số thứ tự của khu khán đài mà làn sóng đang ở sau k giây.

Ràng buộc: ~2 ≤ n ≤ 1000~; ~1 ≤ s ≤ n~; ~1 ≤ k ≤ 10^9~

Ví dụ:

Input:

10 8 5

Output:

3

Giải thích: sóng đi 8 → 9 → 10 → 1 → 2 → 3.

Trận tứ kết World Cup 2026 phải phân định bằng loạt sút luân lưu nghẹt thở! Hai đội A và B, mỗi đội sút n lượt. Thầy Quýt ghi lại kết quả từng lượt: số 1 nghĩa là sút vào, số 0 nghĩa là bị thủ môn cản phá. Hãy cho biết đội nào giành chiến thắng.

Input: Dòng đầu là số nguyên n. Mỗi dòng trong n dòng sau gồm hai số a và b (chỉ nhận giá trị 0 hoặc 1) — kết quả lượt sút của đội A và đội B.

Output: In ra A nếu đội A sút vào nhiều hơn, B nếu đội B sút vào nhiều hơn, hoặc Hoa nếu hai đội bằng nhau.

Ràng buộc: ~1 ≤ n ≤ 100~

Ví dụ 1:

Input:

5
1 0
1 1
0 0
1 1
1 0

Output:

A

Ví dụ 2:

Input:

3
1 1
0 0
1 1

Output:

Hoa

Đội tuyển mà thầy Quýt yêu thích vừa đá xong vòng bảng World Cup 2026 với n trận. Theo luật FIFA: thắng được 3 điểm, hòa được 1 điểm, thua 0 điểm. Ngoài ra hiệu số bàn thắng (tổng bàn ghi được trừ tổng bàn thua) rất quan trọng khi xét vé đi tiếp. Hãy giúp thầy tính thành tích của đội.

Input: Dòng đầu là số nguyên n. Mỗi dòng trong n dòng sau gồm hai số nguyên x và y — số bàn đội ghi được và số bàn đội bị thủng lưới trong một trận.

Output: Một dòng gồm hai số: tổng điểm và hiệu số bàn thắng, cách nhau bởi một dấu cách.

Ràng buộc: ~1 ≤ n ≤ 1000~; ~0 ≤ x, y ≤ 20~

Ví dụ:

Input:

3
2 1
0 0
1 3

Output:

4 -1

Giải thích: thắng 2-1 (+3 điểm), hòa 0-0 (+1 điểm), thua 1-3 (+0 điểm). Tổng điểm 4, hiệu số ~(2+0+1) - (1+0+3) = -1~.

Huấn luyện viên Quýt nghĩ ra bài tập chuyền bóng theo dãy số nổi tiếng nhất lịch sử toán học: phút thứ nhất cả đội chuyền 1 đường, phút thứ hai chuyền 1 đường, và từ phút thứ ba trở đi, số đường chuyền của mỗi phút bằng tổng số đường chuyền của hai phút liền trước: 1, 1, 2, 3, 5, 8, 13, 21, ...

Cho số nguyên dương n, hãy in ra số đường chuyền ở phút thứ n, biết ~F(1) = 1~, ~F(2) = 1~ và ~F(n) = F(n-1) + F(n-2)~ với ~n ≥ 3~.

Input: Một số nguyên dương n.

Output: Giá trị của ~F(n)~.

Ràng buộc: ~1 ≤ n ≤ 90~. Gợi ý: ~F(90)~ là số rất lớn, vượt xa phạm vi kiểu int.

Ví dụ 1:

Input:

6

Output:

8

Ví dụ 2:

Input:

1

Output:

1

Để ra đề nâng cao, Thầy Quýt cần tìm số nguyên tố thứ k trong dãy các số nguyên tố 2, 3, 5, 7, 11, … Hãy giúp thầy tìm số đó.

Input: Một số nguyên k.

Output: Số nguyên tố thứ k.

Ràng buộc: 1 ≤ k ≤ 1000

Ví dụ:

Input:

5

Output:

11

Một số được gọi là đối xứng nếu đọc từ trái sang phải giống hệt đọc từ phải sang trái (ví dụ 121, 1331). Thầy giáo cho số ~n~, hãy kiểm tra nó có đối xứng không.

Input: Một số nguyên ~n~.

Output: In Doi xung nếu đúng, ngược lại in Khong.

Ràng buộc: ~1 ≤ n ≤ 1 000 000 000~

Ví dụ:

Input:

121

Output:

Doi xung

Bắt đầu từ số ~n~, Thầy giáo lặp lại quy tắc: nếu số hiện tại chẵn thì chia đôi, nếu lẻ thì nhân 3 rồi cộng 1. Kỳ lạ là dãy luôn về được 1. Hãy đếm xem cần bao nhiêu bước biến đổi để ~n~ về đến 1.

Input: Một số nguyên ~n~.

Output: Số bước biến đổi. (Nếu ~n~ đã bằng 1 thì cần 0 bước.)

Ràng buộc: 1 ≤ n ≤ 1000

Ví dụ: Input:

6

Output:

8

Thầy Quýt xếp kẹo thành một kim tự tháp lệch: dòng thứ i (đếm từ 1) có (n - i) dấu cách ở đầu, tiếp theo là i dấu *. Hãy in tháp gồm n dòng.

Input: Một số nguyên n.

Output: n dòng theo mô tả trên.

Ràng buộc: 1 ≤ n ≤ 50

Ví dụ:

Input:

4

Output:

   *
  **
 ***
****

Đầu buổi học, Thầy giáo điểm danh lớp có ~n~ học sinh bằng cách gọi số thứ tự từ 1 đến ~n~. Hãy in ra các số thứ tự đó.

Input: Một số nguyên ~n~.

Output: Các số từ 1 đến ~n~, cách nhau một dấu cách.

Ràng buộc: 1 ≤ n ≤ 1000

Ví dụ:

Input:

5

Output:

1 2 3 4 5

Sau bài kiểm tra, Thầy giáo có điểm của ~n~ học sinh. Một bạn được coi là "đạt" nếu điểm từ 5 trở lên. Hãy đếm xem có bao nhiêu bạn đạt.

Input: Dòng đầu là số nguyên ~n~. Dòng sau gồm ~n~ số nguyên là điểm các bạn.

Output: Số học sinh đạt.

Ràng buộc: 1 ≤ n ≤ 1000; 0 ≤ điểm ≤ 10

Ví dụ:

Input:

5
4 5 6 3 8

Output:

3

Mỗi học sinh ở ThinkEdu có một mã số. Thầy giáo muốn tính tổng các chữ số trong mã số ~n~ để làm mã kiểm tra.

Input: Một số nguyên ~n~.

Output: Tổng các chữ số của ~n~.

Ràng buộc: 1 ≤ n ≤ 1 000 000 000

Ví dụ:

Input:

12345

Output:

15

Phần mềm chấm của ThinkEdu chỉ chấp nhận điểm hợp lệ, tức là một số nguyên từ 0 đến 10. Thầy giáo nhập điểm cho một bạn; nếu nhập sai (nhỏ hơn 0 hoặc lớn hơn 10) thì phải nhập lại, cho đến khi nhập được một điểm hợp lệ. Hãy cho biết Thầy giáo đã nhập tất cả bao nhiêu lần.

Input: Lần lượt các số nguyên, mỗi số một dòng, cho đến khi xuất hiện một số hợp lệ (từ 0 đến 10) thì dừng.

Output: Tổng số lần đã nhập (tính cả lần nhập đúng cuối cùng).

Ràng buộc: Mỗi số nhập có giá trị tuyệt đối không quá 1000.

Ví dụ:

Input:

-3
15
8

Output:

3

Thầy giáo phát kẹo cho các số thứ tự từ 1 đến ~n~, nhưng để trêu cả lớp, thầy bỏ qua (không phát) những bạn có số thứ tự chia hết cho ~k~. Hãy tính tổng số thứ tự của những bạn được nhận kẹo.

Input: Hai số nguyên ~n, k~.

Output: Tổng số thứ tự các bạn được nhận kẹo.

Ràng buộc: ~1 ≤ n ≤ 100000; 1 ≤ k ≤ 1000~

Ví dụ:

Input:

10 3

Output:

37

Thầy giáo cầm danh sách điểm của ~n~ học sinh xếp theo thứ tự chỗ ngồi. Thầy muốn trao thưởng cho bạn đầu tiên (theo thứ tự) đạt từ ~m~ điểm trở lên. Hãy in ra số thứ tự chỗ ngồi của bạn đó. Nếu cả lớp không ai đạt, in ~-1~.

Input: Dòng đầu là hai số nguyên ~n, m~. Dòng sau gồm ~n~ số nguyên là điểm theo thứ tự.

Output: Số thứ tự bạn đầu tiên đạt ~m~ điểm, hoặc ~-1~.

Ràng buộc: ~1 ≤ n ≤ 1000; 0 ≤ m, điểm ≤ 10~

Ví dụ: Input:

5 8
5 7 9 6 10

Output:

3

Thầy giáo xếp ghế trong phòng học thành một hình chữ nhật gồm ~h~ hàng, mỗi hàng ~w~ chiếc ghế (mỗi ghế ký hiệu bằng dấu ~*~). Hãy in sơ đồ phòng học.

Input: Hai số nguyên ~h, w~.

Output: ~h~ dòng, mỗi dòng gồm ~w~ dấu ~*~ liền nhau.

Ràng buộc: ~1 ≤ h, w ≤ 50~

Ví dụ:

Input:

2 3

Output:

***
***

Nhân dịp trang trí lớp, Thầy Quýt muốn in một hình bậc thang: dòng thứ i có đúng i dấu *. Hãy in hình bậc thang gồm n dòng.

Input: Một số nguyên n.

Output: n dòng; dòng thứ i gồm i dấu * liền nhau.

Ràng buộc: 1 ≤ n ≤ 50

Ví dụ:

Input:

4

Output:

*
**
***
****

Thầy giáo có ~n~ học sinh và muốn chia thành các nhóm đều nhau (mỗi nhóm có số bạn bằng nhau, không thừa ai). Hỏi có bao nhiêu cách chọn số bạn trong một nhóm? (Chia thành 1 nhóm gồm cả lớp, hay mỗi bạn một nhóm, đều được tính.)

Input: Một số nguyên ~n~.

Output: Số cách chia (chính là số ước của ~n~).

Ràng buộc: 1 ≤ n ≤ 1 000 000

Ví dụ: Input:

6

Output:

4

Thầy Quýt muốn dạy về số nguyên tố (số tự nhiên lớn hơn 1 và chỉ chia hết cho 1 và chính nó). Cho số n, hãy kiểm tra n có phải số nguyên tố không.

Input: Một số nguyên n.

Output: In Nguyen to nếu đúng, ngược lại in Khong.

Ràng buộc: 1 ≤ n ≤ 1 000 000

Ví dụ:

Input:

7

Output:

Nguyen to

Trong danh sách n điểm của lớp, Thầy Quýt muốn biết có bao nhiêu cặp học sinh (không phân biệt thứ tự) có điểm bằng nhau.

Input: Dòng đầu là số nguyên n. Dòng sau gồm n số nguyên là điểm.

Output: Số cặp có điểm bằng nhau.

Ràng buộc: 1 ≤ n ≤ 1000; 0 ≤ điểm ≤ 10

Ví dụ:

Input:

5
5 7 5 7 5

Output:

4