Tên bài: Độ Bền

Năm 1973, nhà Toán học Neil Sloan đã đưa ra khái niệm độ bền của một số nguyên không âm ~ N ~ như sau:

• Nếu ~ N ~ có một chữ số thì độ bền của ~ N ~ là 0.
• Nếu ~ N ~ có từ hai chữ số trở lên thì độ bền của ~ N ~ bằng độ bền của tích các chữ số của ~ N ~ cộng thêm 1.

Yêu cầu: Hãy tính độ bền của số ~ N ~, với ~ 0 \leq N \leq 1,000,000 ~.

Dữ liệu vào

• Dữ liệu vào gồm một số nguyên ~ N ~.

Dữ liệu ra

• Kết quả là một số nguyên duy nhất, chính là độ bền của ~ N ~.

Ràng buộc

• ~ 0 \leq N \leq 1,000,000 ~

Ví dụ

Dữ liệu vào

77

Dữ liệu ra

4

Giải thích:

• Độ bền của ~ 77 ~ được tính như sau:
  • Độ bền của ~ 77 = ~ Độ bền của ~ 4 \times 9 = 36 + 1 = ~ Độ bền của ~ 3 \times 6 = 18 + 1 = ~ Độ bền của ~ 1 \times 8 = 8 + 1 = 0 + 1 + 1 + 1 + 1 = 4 ~.

Tên bài: Xâu Fibo

Anna rất thích tính đối xứng, một phần vì tên cô cũng là một xâu đối xứng. Một xâu được gọi là đối xứng nếu đọc từ trái sang phải và từ phải sang trái đều giống nhau.

Tại trường, Anna được học về dãy xâu Fibonacci ~ F_0, F_1, F_2, \dots ~ như sau:

• ~ F_1 = \text{'A'} ~
• ~ F_2 = \text{'B'} ~
• ~ F_n = F_{n-1} + F_{n-2} ~ với mọi ~ n \geq 2 ~ (nối hai xâu Fibonacci liền trước lại với nhau).

Như vậy, 5 xâu Fibonacci đầu tiên là: 'A', 'B', 'BA', 'BAB', 'BABBA'.

Anna quan tâm đến vấn đề tìm xâu con đối xứng dài nhất trong xâu Fibonacci ~ F_k ~. Nhiệm vụ của bạn là giúp Anna xác định độ dài của xâu con đối xứng dài nhất trong ~ F_k ~.

Dữ liệu vào

• Gồm một dòng duy nhất là số nguyên ~ k ~ ( ~ 0 \leq k \leq 20 ~ ), được đọc từ file FBS.INP.

Dữ liệu ra

• Ghi ra file FBS.OUT một số nguyên duy nhất là độ dài xâu con đối xứng dài nhất trong xâu Fibonacci ~ F_k ~.

Ràng buộc

• ~ 0 \leq k \leq 20 ~

Ví dụ

Dữ liệu vào (FBS.INP):

3

Dữ liệu ra (FBS.OUT):

1

Dữ liệu vào (FBS.INP):

4

Dữ liệu ra (FBS.OUT):

3

Dữ liệu vào (FBS.INP):

5

Dữ liệu ra (FBS.OUT):

4

Đề bài

Viết chương trình tính tổng của các số nguyên tố nằm trong đoạn [L, R] cho trước.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên dương T, là số bộ dữ liệu thử nghiệm. (1 ≤ T ≤ 106)
• T dòng tiếp theo, mỗi dòng gồm hai số nguyên dương L và R, giới hạn của đoạn. (1 ≤ L ≤ R ≤ 106)

Kết quả

Ghi kết quả ra gồm T dòng, mỗi dòng ghi kết quả tổng của các số nguyên tố nằm trong đoạn [L, R] tương ứng.

Ví dụ

Input

2
1 10
10 20

Output

17
60

Ràng buộc

• Subtask 1: 60% số bộ test có 1 ≤ T ≤ 100 và 1 ≤ L, R ≤ 106.
• Subtask 2: 40% số bộ test có 1 ≤ T ≤ 106 và 1 ≤ L, R ≤ 106.

Tên bài: Số Lượng Bộ Tộc

Có một hòn đảo rất xinh đẹp, thu hút nhiều khách du lịch đến tham quan. Trên đảo có ~ N ~ người thuộc nhiều bộ tộc sinh sống ở đó, dân cư trên đảo rất thân thiện và mến khách. Mỗi người sẽ thuộc một bộ tộc nào đó. Trong đoàn du lịch có một nhà nhân chủng học. Trong quá trình khảo sát, ông đã hỏi từng người mà ông gặp trên đảo câu hỏi duy nhất: Trên đảo, bộ tộc của bạn có bao nhiêu người?.

Từ kết quả khảo sát đó, ông đã xác định được số bộ tộc khác nhau tồn tại trên đảo.

Yêu cầu

Cho số ~ N ~ và các câu trả lời. Hãy xác định số bộ tộc có trên đảo. (Dữ liệu vào của bài toán đảm bảo luôn đúng).

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~ N ~ ( ~ 1 \leq N \leq 1,000,000 ~ ).
• Mỗi dòng trong ~ N ~ dòng sau, chứa một số nguyên (~< 20~) chính là câu trả lời nhận được.

Dữ liệu ra

• Một số nguyên duy nhất là số bộ tộc có trên đảo.

Ví dụ

Dữ liệu vào (BOTOC.INP):

3
1
1
1

Dữ liệu ra (BOTOC.OUT):

3

Dữ liệu vào (BOTOC.INP):

7
3
1
2
1
3
2
3

Dữ liệu ra (BOTOC.OUT):

4