Cho một kí tự ~c~. Liệu ~c~ có phải một chữ cái thuộc bảng chữ cái tiếng Anh hay không? Hãy kiểm tra xem!

Input

Gồm một ký tự ~c~ duy nhất.

Output

In ra YES nếu ~c~ thuộc bảng chữ cái tiếng Anh, ngược lại in ra NO.

Sample Test 1

Input:

a

Output:

YES

Sample Test 2

Input:

@

Output:

NO

Cho số nguyên dương ~n~. Hãy đưa ra số lượng chữ số của ~n~ và tổng các chữ số trong biểu diễn thập phân của ~n~.

Input

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

Output

Gồm hai dòng, dòng thứ nhất chứa số chữ số và dòng thứ hai chứa tổng chữ số của ~n~.

Sample Test

Input:

69

Output:

2
15

Cho số nguyên dương ~n~, hãy tìm số Fibonacci thứ ~n~.

Số Fibonacci thứ ~i~ được định nghĩa như sau: ~ \begin{equation} f_i = \begin{cases} 1 & \text{nếu $i \leq 2$}\\ f_{i - 1} + f_{i - 2} & \text{nếu $i > 2$} \end{cases} \end{equation} ~

Ví dụ dãy Fibonacci cho ~10~ số đầu tiên: ~1, 1, 2, 3, 5, 8, 13, 21, 34, 55~.

Input

Gồm một số nguyên dương ~n~ duy nhất. (~n \leq 75~)

Output

In ra số Fibonacci thứ ~n~.

Subtasks

Subtask ~1~ (~40\%~): ~n \leq 40~.

Subtask ~2~ (~60\%~): Không có điều kiện gì thêm.

Sample Test 1

Input:

4

Output:

3

Sample Test 2

Input:

10

Output:

55

Cho số nguyên dương ~n~, hãy kiểm tra xem ~n~ có phải là số nguyên tố hay không.

Input

Gồm một số nguyên ~n~ duy nhất (~n \leq 10^9~)

Output

In ra YES nếu ~n~ là số nguyên tố, ngược lại thì in ra NO.

Subtasks

Subtask ~1~ (~40\%~): ~n \leq 10^3~.

Subtask ~2~ (~60\%~): Không có điều kiện gì thêm.

Sample Test

Input:

3

Output:

YES

Cho số nguyên dương ~k~, hãy liệt kê tất cả số nguyên tố từ ~1~ đến ~k~.

Input

Gồm một số nguyên dương ~k~ duy nhất. (~1 < k \leq 10^5~)

Output

Gồm nhiều dòng, mỗi dòng lần lượt chứa một số nguyên tố trong khoảng ~[1, k]~. Các số được in theo thứ tự từ bé đến lớn.

Sample Test 1

Input:

3

Output:

2
3

Sample Test 2

Input:

14

Output:

2 
3 
5 
7 
11
13

Cho số nguyên dương ~n~, hãy phân tích ~n~ thành tích các thừa số nguyên tố và in ra chúng.

Input

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

Output

Gồm một dòng chứa các thừa số nguyên tố theo thứ tự từ bé đến lớn, mỗi số cách nhau một dấu cách.

Subtasks

Subtask ~1~ (~40\%~): ~n \leq 10^5~.

Subtask ~2~ (~60\%~): Không có điều kiện gì thêm.

Sample Test

Input:

60

Output:

2 2 3 5

Cho hai số nguyên dương ~a~ và ~b~. Hãy tìm ước chung lớn nhất và bội chung nhỏ nhất của hai số đó.

Input

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

Output

Gồm hai dòng, dòng đầu tiên chứa ước chung lớn nhất và dòng thứ hai chứa bội chung nhỏ nhất của ~a~ và ~b~.

Sample Test

Input:

2
5

Output

1
10

Cho số nguyên dương ~n~. Kiểm tra xem ~n~ có phải là số đối xứng hay không.

Các số đối xứng là các số không thay đổi khi viết theo thứ tự từ trái sang phải hoặc từ phải sang trái.

Input

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

Output

In ra YES nếu ~n~ là số đối xứng, ngược lại in ra NO.

Sample Test 1

Input:

123

Output:

NO

Sample Test 2

Input:

121

Output:

YES

Cho số nguyên dương ~n~. Hãy xây dựng tam giác cân ~n~ dòng sử dụng dấu *.

Input

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

Output

• Gồm ~n~ dòng gồm các dấu * biểu diễn một hình tam giác cân.
  
  

Sample Input 1

Input:

1

Output:

*

Sample Input 2

Input:

3

Output:

  *
 ***
*****

Sample Input 3

Input:

5

Output:

    *
   ***
  *****
 *******
*********

Cho bốn số thực ~𝐴, 𝐵, 𝐶, 𝐷~. Hỏi tích của bốn số đó là số dương, số âm hay số ~0~.

Dữ liệu nhập vào từ file TBS.INP:

Gồm bốn dòng, mỗi dòng gồm một số thực lần lượt là bốn số ~𝐴, 𝐵, 𝐶, 𝐷~ ~(−10^{18} ≤ 𝐴, 𝐵, 𝐶, 𝐷 ≤ 10^{18})~.

Kết quả ghi ra file TBS.OUT:

Một số nguyên duy nhất là:

• ~1~ nếu tích bốn số là số dương~;~
• ~-1~ nếu tích bốn số là số âm~;~
• ~0~ nếu tích bốn số là số ~0.~

Ví dụ

Input

20.21
-1.2
-2.3
1.0

Output

1

Input

5.0
-8.9
0.0
123.456

Output

0

Cho một số nguyên dương ~N~. Đếm xem có bao nhiêu số nguyên không âm nhỏ hơn ~N~ và có tận cùng là chữ số ~K~.

Input:

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(N≤10^9)~.
• Dòng thứ hai chứa số nguyên ~K~ ~(0≤K≤9)~.

Output:

Một số nguyên duy nhất là số lượng số thoả mãn yêu cầu đề bài.

Ràng buộc

• Có ~70\%~ số test ứng với ~70\%~ số điểm của bài thoả mãn: ~N≤10^6~;
• ~30\%~ số test còn lại ứng với ~30\%~ số điểm của bài không có ràng buộc gì thêm.

Sample Test

Input:

68
3

Output

7

Giải thích

Các số thoả mãn là: ~3,13,23,33,43,53,63~.

Số trùng là một số tự nhiên mà chữ số đầu tiên trùng với chữ số cuối cùng. Ví dụ: ~8, 66, 686, 8398,...~

Nhập vào một số tự nhiên ~N~ là số trùng. Hãy đếm xem có bao nhiêu số trùng nhỏ hơn ~N~ mà có chữ số đầu và chữ số cuối giống như ~N~.

Ví dụ: ~N = 131~, có các số thoả mãn: ~121, 111, 101, 11, 1~. Vậy có ~5~ số thoả mãn.

Input

Số tự nhiên ~N~ ~(N \le 10^9)~.

Output

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

Sample Test

Input

131

Output

5

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 dãy số ~A: 1, 4, 9, 16, 25, 36, 49, 64, …~

Chỉ lấy các số hàng đơn vị của dãy số ~A~ ta được dãy số ~B: 1, 4, 9, 6, 5, 6, 9, 4, …~

Yêu cầu: Nhập vào một số tự nhiên ~𝑁~. Hãy in ra tổng ~𝑁~ số hạng đầu tiên của dãy số ~B~.

Input

Gồm một số nguyên dương ~N~ ~(N \le 10^9)~.

Output

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

Sample Test

Input

4

Output

20

Cho một dãy số nguyên ~A~ gồm ~N~ phần tử ~A_1,A_2,…,A_N~. In ra độ dài của dãy con liên tiếp đan dấu dài nhất. (Đan dấu là không có hai phần tử nào cạnh nhau mà có cùng dấu)

Input:

• Dòng đầu tiên gồm một số nguyên dương ~N~ ~(N≤10^5)~ là số lượng phần tử của dãy ~A~.
• Dòng thứ hai gồm ~N~ số nguyên ~A_1,A_2,…,A_N~ mô tả dãy ~A~ ~(0<|A_i|≤10^9)~.

Output:

Ghi ra một số nguyên duy nhất là độ dài của dãy con liên tiếp đan dấu dài nhất.

Ràng buộc

• Có ~60\%~ số test ứng với ~60\%~ số điểm có ~N≤10^3~;
• ~40\%~ số test còn lại ứng với ~40\%~ số điểm không có ràng buộc gì thêm.

Sample Test 1

Input:

9
1 3 -1 3 -2 4 -5 -6 7

Output

6

Giải thích

Dãy đan dấu: 3 -1 3 -2 4 -5

Sample Test 2

Input:

9
1 3 -1 3 -2 4 -5 6 7

Output

7

Giải thích

Dãy đan dấu 3 -1 3 -2 4 -5 6