Cho một số ~n~, bạn hãy in ra cụm từ TDZ ra màn hình ~n~ lần, mỗi dòng ~1~ cụm từ.

Input

• Gồm một số nguyên dương ~n~ ~(n \leq 100)~.

Output

• In ra theo yêu cầu đề bài.

Sample Test

Input

5

Output

TDZ
TDZ
TDZ
TDZ
TDZ

Cho ba số ~a, b, c~. In ra YES nếu có 2 trong ba số có tổng lớn hơn ~10~, ngược lại in ra NO.

Input

• Một dòng gồm ba số nguyên ~a, b, c.~ (~a, b, c \leq 10~)

Output

• In ra theo yêu cầu đề bài.

Sample Test

Input

1 2 3

Output

NO

Cho hai số tự nhiên ~a~ và ~b~. Hãy tính xem ~2~ số này cách nhau bao nhiêu đơn vị.

Input

• Dòng thứ nhất chứa số tự nhiên ~a~ (~a \leq 1000~).
• Dòng thứ hai chứa số tự nhiên ~b~ (~b \leq 1000~).

Output

• In ra kết quả của bài toán.

Sample Test 1

Input:

10
4

Output:

6

Sample Test 2

Input:

1
3

Output:

2

Cho ~a, b~ là độ dài 2 cạnh đáy và ~h~ là chiều cao của một hình thang. Tính diện tích hình thang đó.

Input

• Gồm một dòng chứa ~3~ số thực ~a, b, h~ (~a, b, h \leq 1000~).

Output

• In ra diện tích hình thang. Kết quả được tính đến chữ số thập phân thứ 3.

Sample Test

Input

5 3 2 

Output

8

Cho bốn số nguyên dương ~a, b, c, d~. Hãy so sánh ~\frac {a} {b}~ với ~\frac {c} {d}~.

Input

• Gồm một dòng chứa bốn số nguyên dương ~a, b, c, d~ (~a, b, c, d \leq 10^9~).

Output

• In ra > nếu ~\frac {a} {b} > \frac {c} {d}~.
• In ra < nếu ~\frac {a} {b} < \frac {c} {d}~.
• In ra = nếu ~\frac {a} {b} = \frac {c} {d}~.

Sample Test

Input

1 2 3 4

Output

<

Note

• ~\frac {1} {2} < \frac {3} {4}~.

TDZ quan niệm rằng, một số không may mắn là số chia hết cho ~5~ hoặc chia cho ~5~ dư ~3~.

Vi dụ các số may mắn: ~1, 2, 4, 6, 7, 9, 11, 12, 14~.

Biết rằng TDZ chỉ sử dụng tất cả các số may mắn nhỏ hơn ~N~ đánh số thứ tự các bạn học sinh để gửi lời chúc kiểm tra thật tốt. Hãy tính tổng các số may mắn đã được sử dụng.

Input

• Gồm một số nguyên dương ~N~ duy nhất. (~N \leq 10^8~)

Output

• In ra tổng các số may mắn nhỏ hơn ~N~.

Sample Test

Input

15

Output

66

Note

• Các số may mắn nhỏ hơn ~N~ là ~1, 2, 4, 6, 7, 9, 11, 12, 14~ và tổng của chúng bằng ~66~.

Cho một xâu ~S~, hãy in ra xâu đảo ngược của xâu đó.

Input

Gồm một xâu ~S~ duy nhất có độ dài không vượt quá ~1000~ ký tự.

Output

In ra xâu ~S~ đó theo thứ tự đảo ngược.

Sample Test

Input:

abc

Output:

cba

Cho dãy kí tự S, hãy chỉ ra vị trí của dấu cách đầu tiên từ trái sang phải của xâu S.

Input

Gồm một dòng chứa dãy ký tự S có độ dài không quá ~1000~ ký tự.

Output

In ra vị trí dấu cách đầu tiên (đánh số bắt đầu từ 0). Nếu không tồn tại dấu cách nào in ra -1.

Sample Test 1

Input:

abc cba ddd

Output:

3

Sample Test 2

Input:

abcd

Output:

-1

Trên một màn hình LED lớn, người ta lần lượt cho hiện ra các số tự nhiên từ ~0~ đến ~9~ và cứ lặp đi lặp lại như thế (tức là sau số ~9~ là số ~0~).

Ban đầu, giây thứ ~0~, màn hình xuất hiện số ~K~ ~(0 ≤ K ≤ 9)~, sau ~1~ giây sẽ chuyển số tiếp theo.

Hỏi sau ~N~ giây, màn hình đang hiển thị số mấy?

Yêu cầu: Nhập vào ~N, K~. In ra số đang hiển thị ở giây thứ ~N~.

Input

• Gồm hai số nguyên ~N, K~ ~(K \le 9; N \le 10^9)~.

Output

• In ra một số nguyên duy nhất là kết quả của bài toán.

Sample Test

Input

5
0

Output

5

Cho một dãy gồm ~N~ số nguyên dương ~a_1, a_2, a_3, ..., a_N~ và một số nguyên ~x~. Tìm số lớn nhất trong dãy sao cho số đó nhỏ hơn số ~X~.

Input

• Dòng thứ nhất chứa số nguyên dương ~N~ (~N \leq 10^5~).
• Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, a_3, ... a_N~. (~a_i \leq 10^6~)
• Dòng thứ ba chứa số nguyên ~X~. (~|X| \leq 10^6~)

Output

• In ra số lớn nhất nhỏ hơn ~X~ trong dãy. Nếu không tồn tại số nào thì in ra -1.

Sample Test 1

Input

5
1 2 6 4 5
4

Output

2

Sample Test 2

Input

4
1 2 3 4
0

Output

-1

Cho số nguyên dương ~N~. Đếm xem trong các chữ số của ~N~ có bao nhiêu số nguyên tố.

Input

• Gồm một số nguyên dương ~N~ duy nhất.
  
  

Output

• In ra số lượng chữ số là số nguyên tố trong ~N~.
  
  

Subtasks

• Subtask 1 (~50\%~ số điểm): ~N \leq 10^4~.
• Subtask 2 (~20\%~ số điểm): ~N \leq 10^8~.
• Subtask 3 (~30\%~ số điểm): ~N \leq 10^{100}~.
  
  

Sample Test

Input

23452345

Output

6

Note

• Có ~6~ chữ số nguyên tố trong ~N~ là ~2, 3, 5, 2, 3, 5~.

Cho một dãy gồm ~N~ số nguyên dương ~a_1, a_2, a_3, ..., a_N~. Biết rằng các số trong dãy đều xuất hiện hai lần, trừ một số. Hãy tìm số đó.

Input

• Dòng thứ nhất chứa số nguyên dương ~N~.
• Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, a_3, ... a_N~. (~a_i \leq 10^6~)
• Các số đều xuất hiện hai lần trừ một số.

Output

• In ra số chỉ xuất hiện một lần trong dãy.

Subtasks

• Subtask 1 (~20\%~ số điểm): ~N = 3~.
• Subtask 2 (~30\%~ số điểm): ~N \leq 10^3~.
• Subtask 3 (~50\%~ số điểm): ~N \leq 10^6~.

Sample Test 1

Input

5
4 1 2 1 2

Output

4

Một số nguyên dương ~A~ được gọi là hoàn hảo nếu ~2 \times A \leq K~, với ~K~ là tổng các ước dương của ~A~.

Ví dụ, ~12~ là số hoàn hảo vì ~2 * 12 \leq K~ với ~K = 1 + 2 + 3 + 4 + 6 + 12 = 28.~

Cho ~N~ số nguyên dương ~A_1, A_2, \ldots, A_n~, hãy đếm số lượng số hoàn hảo trong dãy đã cho.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~. (~N \leq 10^4~)
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên dương ~A_i~. (~A_i \leq 10^6~)

Output

• In ra số lượng số hoàn hảo trong dãy đã cho.

Sample Test

Input:

5
8
16
12
6
7

Output:

2

Cho một dãy gồm ~N~ số nguyên ~a_1, a_2, a_3, ..., a_N~. Hãy tìm đoạn con liên tiếp và dài nhất mà các phần tử liên tiếp cách đều nhau.

Input

• Dòng thứ nhất chứa số nguyên dương ~N~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, a_3, ... a_N~. (~|a_i| \leq 10^9~)

Output

• In ra độ dài của đoạn con dài nhất thoả mãn đề bài.

Subtasks

• Subtask 1 (~20\%~ số điểm): ~N = 3~.
• Subtask 2 (~30\%~ số điểm): ~N \leq 10^3~.
• Subtask 3 (~50\%~ số điểm): ~N \leq 10^6~.

Sample Test 1

Input

3
1 2 1

Output

3

• Dãy đã cho có các số liên tiếp cách nhau ~1~ đơn vị nên đây là dãy con dài nhất thoả mãn.

Sample Test 2

Input

6
1 2 3 5 7 9

Output

4

Note

• Dãy con liên tiếp dài nhất và cách đều nhau là ~3, 5, 7, 9~. (khoảng cách giữa các số liên tiếp đều là ~2~)

Sample Test 3

Input

6
1 4 7 4 7 1

Output

5

Note

• Dãy con liên tiếp dài nhất và cách đều nhau là ~1, 4, 7, 4, 7~. (khoảng cách giữa các số liên tiếp đều là ~3~)

Cho dãy số có quy luật như sau: ~1,2,2,3,3,3,4,4,4,4,5,5,…~ Cho một số tự nhiên ~N~, hãy tìm số thứ ~N~ của dãy số trên (các số được đánh thứ tự từ ~1~).

Input

• Gồm một số nguyên dương ~N~ ~(N ≤ 10^{15})~.

Output

• In ra kết quả của bài toán.

Subtasks

• Subtask 1 (~60\%~ số điểm): ~N ≤ 10^{6}~;
• Subtask 2 (~20\%~ số điểm): ~N ≤ 10^{10}~;
• Subtask 3 (~20\%~ số điểm): Không có ràng buộc gì thêm.

Sample Test

Input

5

Output

3

Cho một dãy gồm ~N~ số nguyên ~a_1, a_2, a_3, ..., a_N~. Hãy tìm một đoạn con liên tiếp trong dãy sao cho chúng có tổng lớn nhất.

Input

• Dòng thứ nhất chứa số nguyên dương ~N~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, a_3, ... a_N~. (~|a_i| \leq 10^9~)

Output

• In ra tổng lớn nhất tìm được.

Subtasks

• Subtask 1 (~20\%~ số điểm): ~N = 3~.
• Subtask 2 (~20\%~ số điểm): ~N \leq 100~.
• Subtask 3 (~30\%~ số điểm): ~N \leq 10^3~.
• Subtask 4 (~30\%~ số điểm): ~N \leq 10^6~.

Sample Test

Input

7
-2 -3 4 -1 -2 1 5

Output

7

Note

• Đoạn con có tổng lớn nhất là ~4, -1, -2, 1, 5~.

Cho một xâu ~S~ gồm các kí tự số. Hãy đếm xem có bao nhiêu xâu con chia hết cho ~4~ (xâu con có thể bắt đầu bằng ~0~).

Một xâu con của ~S~ là xâu được tạo thành từ các ký tự liên tiếp trong ~S~.

Input

• Gồm một xâu ~S~ có độ dài không quá ~10^6~.

Output

• In ra kết quả của bài toán.

Subtasks

• Subtask 1 (~60\%~ số điểm): Xâu ~S~ có độ dài không quá ~100~.
• Subtask 2 (~40\%~ số điểm): Không có ràng buộc gì thêm.

Sample Test 1

Input

08

Output

3

Note

• Các xâu con thoã mãn là ~0, 8, 08~.

Sample Test 2

Input

13085

Output

5

Viết liền các số nguyên dương liên tiếp, từ nhỏ đến lớn, bắt đầu từ ~1~, ta sẽ được một dãy dài vô hạn gồm các chữ số: ~123456789101112131415161718192021222324252627282930313233343536\ldots~

Bạn được cho số nguyên dương ~k~, nhiệm vụ của bạn là tìm chữ số thứ ~k~ của dãy trên.

Input

• Dòng thứ nhất chứa số nguyên dương ~T~ - số bộ dữ liệu. (~T \leq 10^3~)
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~k~.

Output

• In ra ~T~ dòng, mỗi dòng chứa một chữ số cho bộ dữ liệu tương ứng.

Subtasks

• Subtask 1 (~20\%~ số điểm): Mọi số ~k \leq 50~.
• Subtask 2 (~30\%~ số điểm): Mọi số ~k \leq 10^6~.
• Subtask 3 (~50\%~ số điểm): Mọi số ~k \leq 10^{18}~.

Sample Test

Input

5
8
18
16
14
19

Output

8
1
1
1
4

Cho số nguyên dương ~N~. Hãy đếm số cách xoá đi một đoạn chữ số liên tiếp của ~N~ (không được xoá hết) để nhận được số mới chia hết cho ~3~, biết rằng số mới nhận được có thể có thừa chữ số ~0~ ở đầu.

Hai cách xoá được coi là khác nhau nếu có một vị trí được xoá trong cách này nhưng không được xoá trong cách kia.

Input

• Gồm một dòng duy nhất chứa một số nguyên ~N~ (~1 \le N \le 10^{100000}~).

Output

• In ra một số nguyên là số cách xoá tìm được.

Subtasks

• Subtask 1 (~50\%~ số điểm): ~N \le 10^{300}~.
• Subtask 2 (~25\%~ số điểm): ~N \le 10^{10000}~.
• Subtask 3 (~25\%~ số điểm): Không có ràng buộc gì thêm.

Sample Test 1

Input

1005

Output

4

Sample Test 2

Input

2009

Output

3