Bạn được cho 2 số nguyên dương \(n\), \(k\) .Hãy tìm số thứ \(k\) không chia hết cho \(n\)

Ví dụ: \(n=3\), \(k=7\) Tất cả các số không chia hết cho \(n\) là \(1,2,4,5,7,8,10,11,13,…\) Vậy số thứ \(k\) không chia hết cho \(3\) là số \(10\).

Input

• Dòng đầu tiền : Số nguyên dương \(q\) \((q \leq 1000)\)- số câu hỏi
• \(q\) dòng tiếp theo chứa 2 số nguyên dương \(n\) và \(k\) \((2 \leq n \leq 10^9, 1 \leq k \leq 10^9)\)

Output

• Gồm \(q\) dòng, mỗi dòng chứa số nguyên dương thứ \(k\) không chia hết cho \(n\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n,k \leq 10^5\)
• Subtask \(2\) (\(50\%\) số điểm): \(n,k \leq 10^9\)

Example

6
3 7
4 12
2 1000000000
7 97
1000000000 1000000000
2 1 

10
15
1999999999
113
1000000001
1

Xâu \(A\) được gọi là hậu tố của xâu \(B\) nếu length(\(A\)) <= length(\(B\)) và sau khi ta xóa đi một số kí tự đầu tiên của \(B\) thì thu được xâu \(A\).

Yêu cầu: Cho \(N\) xâu, bạn hãy tìm một xâu dài nhất sao cho nó là hậu tố của ít nhất \(2\) trong số \(N\) xâu đã cho. Nếu có nhiều xâu thỏa mãn có cùng độ dài, hãy đưa ra đáp án xuất hiện đầu tiên theo thứ tự từ điển.

Dữ liệu vào

• Dòng thứ nhất ghi số nguyên dương \(N\) \((2 ≤ N ≤ 5000)\).
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo ghi xâu \(W_i\) \((2 ≤ length(W_i) ≤ 100)\).

Kết quả

• Gồm một dòng duy nhất ghi xâu hậu tố dài nhất thỏa mãn yêu cầu đề bài, bộ test đảm bảo luôn tồn tại xâu hậu tố thõa mãn.

Sample Input 1

2
AABB
ABB

Sample Output 1

ABB

Sample Input 2

4
BB
BB
AA
AA

Sample Output 2

AA

Giới hạn

• 50% test có N <= 100
• 50% test có N <= 5000

Cho dãy số nguyên \(a_1, a_2, ..., a_n\), các số khác nhau từng đôi một (\(3 \le N \le 5000\); với mọi \(i\) ta có \(|a_i| \le 10^6\)). Bộ ba số \(a_i, a_j, a_k (i \neq j \neq k)\) được gọi là Bộ tam hợp nếu có một số bất kỳ trong ba số đó bằng trung bình cộng của hai số còn lại.

Yêu cầu:

• Hãy đếm số lượng bộ tam hợp và tìm bộ tam hợp có tổng giá trị của ba số là lớn nhất.

Input

• Dòng 1 chứa số N;

• Dòng 2 chứa n số \(a_1, a_2, ..., a_N\) cách nhau ít nhất một dấu cách

Output

• Dòng 1 ghi một số nguyên dương là số lượng bộ tam hợp tìm được;

• Dòng 2 ghi tổng giá trị ba số của bộ tam hợp là lớn nhất.

Example

7
6 1 9 2 3 4 8 

5
18

Cho số nguyên N (\(0 ≤ N ≤ 10^{15}\)).

Yêu cầu:

• Tìm số nguyên dương \(Q\) nhỏ nhất có hơn một chữ số sao cho tích các chữ số của \(Q\) bằng \(N\).

Dữ liệu:

• Dòng thứ nhất ghi số nguyên dương \(T\) (\(2 ≤ T ≤ 100\)) là số lượng test.
• \(T\) dòng tiếp theo, mỗi dòng ghi một số nguyên dương \(N\).

Kết quả:

• Ghi ra gồm \(T\) dòng, mỗi dòng ghi ra số \(Q\) tìm được tương ứng với số \(N\), nếu không tìm được thì ghi ra số \(-1\).

Input:

4
10
16
13
9

Output:

25
28
-1
19

Xâu \(A\) được gọi là tiền tố của xâu \(B\) nếu \(length(A) <= length(B)\) và sau khi ta xóa đi một số kí tự cuối cùng của \(B\) thì thu được xâu \(A\).

Yêu cầu:

• Cho \(N\) xâu, bạn hãy tìm một xâu dài nhất sao cho nó là tiền tố của ít nhất 2 trong số \(N\) xâu đã cho. Nếu có nhiều xâu thỏa mãn có cùng độ dài, hãy đưa ra đáp án xuất hiện đầu tiên theo thứ tự từ điển.

Dữ liệu:

• Dòng thứ nhất ghi số nguyên dương \(N (2 ≤ N ≤ 5000)\).
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo ghi xâu \(W_i (2 ≤ length(W_i) ≤ 100)\).

Kết quả:

• Ghi ra một dòng duy nhất ghi xâu tiền tố dài nhất thỏa mãn yêu cầu đề bài.

Input:

7
CHEDDAR
CHESSO
CHAOURCE
PARMESAN
CHAUMES
ROQUEFORT
POSSIA

Output:

CHA

Giải thích:

• Các xâu là tiền tố của ít nhất 2 xâu là C, CH, CHA, CHE, P. Xâu dài nhất là xâu CHA và CHE nhưng xâu CHA xuất hiện trước CHE trong thứ tự từ điển.

Cho một dãy gồm n số nguyên \(a_1, a_2, a_3, ..., a_n\)

Yêu cầu:

• Hãy tìm trong dãy số trên một số nguyên bằng tổng tất cả các số nguyên còn lại.

Dữ liệu:

• Dòng thứ nhất ghi một số nguyên dương n (\(2 <= n <= 200\)).
• Dòng thứ hai ghi n số nguyên \(a_1, a_2, a_3, ..., a_n\) các số cách nhau ít nhất một dấu cách. Biết rằng \(|a_i| <= 10^9\) với mọi số nguyên i thỏa mãn \(1 <= i <= n\).

Kết quả:

• Ghi ra một số nguyên tìm được trong dãy số đã cho thỏa mãn yêu cầu đề bài. Trường hợp không có số nào trong dãy thỏa mãn yêu cầu đề bài thì ghi một kí tự N.

Input

4
-2 5 3 6

Output

6

Input

3
2 3 4

Output

N

Phân tích nhóm (phân nhóm, chia nhóm) là công việc phân chia các phần tử trong một tập hợp thành một hoặc nhiều nhóm mà trong đó, các phần tử trong cùng một nhóm sẽ giống nhau hơn so với phần tử thuộc nhóm khác.

Yêu cầu:

• Cho một tập N số nguyên dương và một số nguyên dương K, nhiệm vụ của bạn là đếm xem có bao nhiêu nhóm. Biết rằng 2 phần tử được xếp chung nhóm với nhau nếu như chênh lệch giữa chúng không vượt quá K.

Giải thích: Với tập N = 7 số nguyên dương: 2, 6, 1, 7, 3, 4, 9 và K = 1 thì ta sẽ có các mối quan hệ sau:

• 2 và 1 chung một nhóm (chênh lệch giữa chúng là 1, không vượt quá K)
• 2 và 3 chung một nhóm
• 6 và 7 chung một nhóm
• 3 và 4 chung một nhóm

Vậy ta sẽ có 3 nhóm: {1, 2, 3, 4}, {6, 7} và {9}

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên T – là số bộ test cần kiểm tra (\(T ≤ 20\)).

• Các dòng tiếp theo chứa T bộ test, mỗi bộ test gồm 2 dòng:

• Dòng đầu trong mỗi bộ test chứa 2 số nguyên dương N, K (\(1 ≤ N ≤ 10^5, 1 ≤ K ≤ 10^6\)) cách nhau ít nhất 1 dấu cách.

• Dòng thứ hai trong mỗi bộ test chứa N số nguyên dương – là các phần tử của tập hợp (giá trị không vượt quá \(10^6\)).

Kết quả:

• Gồm T dòng, mỗi dòng chứa một số nguyên dương là số nhóm tương ứng của mỗi bộ test.

Input

3
7 1
2 6 1 7 3 4 9
7 2
2 6 1 7 3 4 9
5 5
15 1 20 4 17

Output

3
1
2

Trò chơi rải sỏi là một trò chơi khá đơn giản nhưng thú vị, đòi hỏi người chơi cần phải tính toán hợp lí sao cho mỗi lần chơi được kết quả tốt nhất. Trò chơi được mô tả như sau:

Vật dụng cho trò chơi gồm:

• Một bàn cờ có hình vành khăn, mà trên đó người ta đã chia thành N ô nhỏ bằng nhau, các ô được đánh số liên tục từ 1 đến N theo chiều kim đồng hồ.
• Một số ô đã rải sẵn một số viên sỏi.

Ở hình minh họa, ta có bàn cờ được chia thành 6 ô nhỏ bằng nhau tương ứng với N = 6.

Cách chơi:

Người chơi chọn một ô bất kì có chứa sỏi và lấy hết số sỏi này, sau đó chọn cho mình một chiều đi theo chiều kim đồng hồ hoặc ngược lại và suốt một lượt chơi chỉ đi theo chiều này.

Một lượt chơi gồm 2 bước sau:

• Bước 1: Theo chiều đã chọn, qua mỗi ô rải một viên sỏi bắt đầu từ ô liền kề với ô đã chọn, cứ làm như vậy cho đến hết số viên sỏi đã lấy ra. Gọi ô cuối cùng được rải một viên sỏi vào là ô thứ K.
• Bước 2: Người chơi lấy hết các viên sỏi ở ô kề với ô thứ K (theo chiều đã chọn) và dừng lượt chơi.

Yêu cầu:

• Nếu là người chơi thì với một lượt chơi bạn có thể kiếm được tối đa bao nhiêu viên sỏi?

Dữ liệu vào:

• Dòng đầu tiên ghi số nguyên dương \(N (N <= 100)\).
• Dòng tiếp theo ghi N số nguyên không âm mà số thứ i chính là số viên sỏi đã rải sẵn ở ô thứ i trong bàn cờ (mỗi số cách nhau ít nhất 1 dấu cách). Số sỏi ở mỗi ô trong N ô này đều không vượt quá \(10^{12}\) viên.

Kết quả:

• Ghi ra một số nguyên M là số viên sỏi nhiều nhất có thể lấy ra được trong một lượt chơi.

Input

6
0 3 0 1 4 2

Output

3

Giải thích ví dụ:

• Chọn ô thứ 4 và đi theo chiều ngược chiều kim đồng hồ thì được 3 viên sỏi

Nhập vào từ bàn phím một số nguyên dương N (với 2 <= N <= 100000). Gọi X là tích 1.2.3...N.

Yêu cầu: Tìm số nguyên M là số lượng chữ số 0 tận cùng của số X.

Dữ liệu vào:

• Chứa một số nguyên dương N (với \(2 <= N <= 100000\)).

Kết quả:

• Ghi ra số nguyên M là số lượng chữ số 0 tận cùng của số X.

Input

5

Output

1

Giải thích ví dụ:

X=12345= 120 nên có 1 số 0 (zero) tận cùng.

Nguồn: Bài 1 HSG lớp 9 TPĐN '2015-2016

Một xâu kí tự được gọi là xâu đối xứng nếu ta đọc xâu này từ trái sang phải hoặc từ phải sang trái là như nhau. Chẳng hạn xâu ‘abcba’ là một xâu đối xứng. Cho trước một xâu kí tự S không chứa kí tự trống (dấu cách). Hãy tìm cách cắt xâu S thành 2 xâu (2 xâu này phải khác xâu rỗng) là P và Q (với P là phần đầu, Q là phần còn lại của xâu S) sao cho khi ghép xâu P vào sau xâu Q ta được một xâu kí tự mới là xâu kí tự đối xứng.

Dữ liệu vào:

• Một xâu kí tự S (xâu S có không quá 255 kí tự)

Kết quả:

• Ghi ra một số nguyên k là độ dài của xâu P. Trường hợp không có cách cắt nào thỏa mãn yêu cầu đề bài thì ghi ra một số 0.

Chú ý: Trường hợp có nhiều cách cắt thỏa mãn yêu cầu đề bài thì chọn cách cắt sao cho độ dài của xâu P là nhỏ nhất.

Input

abaabaabaaba

Output

3

Nhập vào từ bàn phím một số nguyên dương \(n\) \((n≤10^{16})\). Hãy tìm và in ra màn hình chữ số lớn nhất của số \(n\).

Input

• Số nguyên dương \(n\)

Output

• Kết quả của bài toán

Example

70128 

8

Cho trước hai số nguyên dương m và n với \(1< m ≤ 10^{15} ; 1 < n ≤ 10^7\) . Hãy xác định có bao nhiêu cặp số nguyên dương \((p; q)\) thỏa mãn đồng thời cả 3 điều kiện: \(p < m; q < n\) và phân số \((m+p)/(n+q)\) có giá trị là một số nguyên.

Dữ liệu vào:

• Dòng thứ nhất chứa số nguyên dương m (\(1< m ≤ 10^{15}\))
• Dòng thứ hai nguyên dương n (\(1< n ≤ 10^7\))

Kết quả:

• Ghi ra một số nguyên k là số cặp số nguyên dương (p;q) thỏa yêu cầu trong đề bài

Input

5
3

Output

1

Giải thích:

• Chỉ có 1 cặp số \((p;q)\) thỏa mãn là \((3;1)\)

Trong bảng mã ASCII, 26 kí tự chữ cái thường từ ‘a’ đến ‘z’ được mã hóa tương ứng bằng các số tự nhiên từ 97 đến 122.

Cho một xâu kí tự S chỉ chứa toàn các kí tự chữ cái thường. Gọi P là xâu mã hóa tương ứng của xâu S bằng cách mã hóa từng ký tự trong S (theo bảng mã ASCII) và viết liên tiếp nhau. Ví dụ: S = ‘ab’ thì P = ‘9798’.

Yêu cầu:

• Hãy viết chương trình nhập vào từ bàn phím một xâu đã mã hóa P (có không quá 255 kí tự) và in ra màn hình xâu kí tự S.

Dữ liệu vào:

• Chứa một xâu đã mã hóa P

Kết quả

• In ra màn hình xâu kí tự S

Input

979899

Output

abc

Input

1009711097110103

Output

danang

http://lequydon.ntucoder.net/Problem/Details/4769

Có 2 số nguyên tố a và b với \(a \ne b\); \(b \ne 2\) và \(b \ne 5\). Tý thực hiện chia \(a : b\) thì được một số x là thập phân vô hạn tuần hoàn.

Yêu cầu:

• Cho trước số nguyên dương \(n\) (\(n \le 10^{16}\)). Hãy tìm chữ số thứ \(n\) sau dấu phẩy của số \(x\).

Input

• Dòng thứ nhất chứa số nguyên tố \(a (a \le 1000)\).
• Dòng thứ hai chứa số nguyên tố \(b (b \ne a; b \ne 2; b \ne 5; b \le 1000)\).
• Dòng thứ ba chứa số nguyên dương \(n (n \le 10^{16})\).

Output

• Ghi ra một chữ số thứ \(n\) sau dấu phẩy của số \(x\).

Example

5
7
15

4

Nhập vào từ bàn phím một số nguyên dương n (\(n ≤ 10^8\)). Hãy tìm và in ra màn hình số nguyên tố nhỏ nhất và lớn hơn số n.

Dữ liệu vào

• Số nguyên dương n

Kết quả

• Kết quả của bài toán

Input

6

Output

7

Trong Học kỳ I vừa qua, Tý đạt được danh hiệu học sinh giỏi nên được bố
thưởng. Biết Tý là học sinh rất đam mê Toán và Tin học nên bố muốn thử thách Tý
bằng một trò chơi có thưởng như sau:

Bố có rất nhiều hộp hình khối lập phương giống nhau xếp thành một hàng thẳng
và được đánh số ký hiệu bằng các số tự nhiên lẻ bắt đầu từ 1; 3; 5;... Trong các hộp đó
HSG Tin học Lớp 9 NH 2018−2019
có duy nhất 1 hộp đựng phần thưởng, các hộp khác là hộp rỗng. Bố cho Tý biết hộp
đựng phần thưởng là hộp chính giữa của một đoạn dài nhất (ít nhất là 3 hộp liên tiếp)
có tổng các số ký hiệu ghi trên các hộp bằng số m.

Yêu cầu:

• Với số m cho trước, hãy tìm số ký hiệu của hộp có chứa phần thưởng.

Dữ liệu vào:

• Gồm một số nguyên dương m (\(m<=10^{16}\)).

Dữ liệu ra:

• Ghi ra một số k là số ký hiệu của hộp
  có chứa phần thưởng.

Input

45

Output

9

Giải thích

Các hộp được đánh số ký hiệu là 1; 3; 5; 7; 9; 11; 13; 15; 17; 19; 21; 23; 25;…
Đoạn dài nhất có tổng các số ký hiệu ghi trên hộp bằng 45 là các hộp có số ký
hiệu 5; 7; 9; 11; 13. Do đó hộp cần tìm có số ký hiệu là 9.

Lan có 1 tấm bìa hình chữ nhật có các kích thước là \(x\) (cm) và \(y\) (cm), (\(x,y\) là số nguyên dương). Lan muốn cắt tấm bìa này thành những hình vuông bằng nhau có độ dài cạnh là số nguyên (đơn vị cm) sao cho tấm bìa được cắt hết không còn thừa mảnh nào. Hỏi Lan có thể cắt được ít nhất mấy hình vuông?

Yêu cầu: Viết chương trình nhập vào \(x,y\) tính và in ra \(m\) - là số lượng hình vuông cần tìm theo yêu cầu trên.

Input

Nhập từ bàn phím 2 số nguyên dương \(x, y (x, y \le 10^9)\), mỗi số trên 1 dòng:

• Dòng đầu chứa số \(x\)
• Dòng thứ hai chứa số \(y\)

Output

• In ra màn hình số lượng hình vuông.

Example

6 
8

12

Hãy viết chương trình thực hiện nhiệm vụ sau:

Nhập vào từ bàn phím một xâu kí tự \(S\), hãy in ra số kí tự chỉ xuất hiện đúng 1 lần trong xâu \(S\).

Input

• Dòng đầu tiên và duy nhất chứa 1 xâu \(S\) (chỉ chứa các kí tự trong tập \(\{a,b,\dots z\}\), không chứa dấu cách) \((|S| \leq 255)\).

Output

• In ra số kí tự chỉ xuất hiện đúng 1 lần trong xâu \(S\).

Example

abbacdmedc 

2

Cho dãy số \(A\) gồm \(n\) phần tử nguyên dương \(A_1,A_2,…,A_n\). Hãy loại một phần tử bất kỳ trong dãy số và đặt \(P\) tích các số còn lại. Phân tích thừa số nguyên tố của \(P\), sau đó tính tổng các số mũ trong thừa số nguyên tố đó. Hãy tìm cách bỏ loại bỏ số nào để tổng các số mũ nhỏ nhất có thể.

Ví dụ: cho dãy số gồm \(4\) số \(1; 2; 4; 10\). có 2 cách bỏ đều cho tổng số mũ bằng \(3\) là nhỏ nhất:

• Cách 1: Loại bỏ số \(4\), ta có \(P=1 * 2*10=20=2^2*5\) có tổng số mũ bẳng \(3\)
• Cách 2: Loại bỏ số \(10,\) ta có \(P=1 * 2*4=8=2^3\) có tổng số mũ bẳng \(3\)

Yêu cầu: Cho dãy số \(A\), hãy in ra tổng số mũ nhỏ nhất của phân tích thừa số sau khi bỏ một phần tử.

Input

• Đọc từ file văn bản TSNT.INP:
• Dòng đầu tiên chứa dãy số \(n\ (n≤10^5)\).
• Dòng thứ 2 chứa \(n\) phần tử của dãy số \(A\ (A_i≤10^6)\).

Output

• Ghi ra file văn bản TSNT.OUT một số nguyên là tổng số mũ nhỏ nhất của phân tích thừa số sau khi bỏ một phần tử.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N≤10^4\) và \(A_i≤3\).
• Subtask \(2\) (\(30\%\) số điểm): \(N≤10^4\) và \(A_i≤8\).
• Subtask \(3\) (\(30\%\) số điểm): \(N≤10^4\) và \(A_i≤10^6\).
• Subtask \(4\) (\(10\%\) số điểm): trường hợp còn lại.

Example

4
1 2 4 10 

3

Cho một xâu ký tự \(S\) chỉ gồm các chữ cái thường a..z. Xâu đối xứng là xâu kí tự mà khi viết từ phải qua trái hay từ trái qua phải thì xâu đó không thay đổi. Ví dụ: \(madam\), \(ioi\) là các xâu đối xứng.

Yêu cầu: Với xâu ký tự \(S\) cho trước, hãy tính số ký tự bỏ đi ít nhất để các ký tự còn lại có thể sắp xếp được thành một xâu đối xứng.

Ví dụ:

• Cho xâu aammmda thì cần bỏ 2 ký tự a và m thì xâu còn lại là ammda và xếp lại thành madam là xâu đối xứng.
• Cho xâu aaabbcc thì không cần bỏ ký tự thì xâu đó xếp lại thành bcaaacb là xâu đối xứng.

Input

• Một xâu ký tự \(S\) có \(n\) ký tự (\(n \le 10^5\)) chỉ gồm các ký tự chữ cái thường a..z.

Output

• Một số nguyên là số lượng ký tự ít nhất cần bỏ để các ký tự còn lại có thể sắp xếp được thành một xâu đối xứng.

Scoring

• Subtask \(1\): (\(30\%\) số điểm): chỉ chứa 2 ký tự a và b.
• Subtask \(2\): (\(30\%\) số điểm): chỉ chứa 3 loại ký tự bất kỳ.
• Subtask \(3\): (\(40\%\) số điểm): trường hợp còn lại.

Example

aammmda

2

aaabbcc

0

Cho dãy số \(A\) gồm \(n\) phần tử nguyên dương \(A_1,A_2,…,A_n\). Mỗi phần tử có giá trị không vượt quá \(10^9\) và \(n≤ 10^5\). Một cặp số được gọi là cặp tương đồng với \(x\), nếu cặp số này có tổng bằng số \(x\) cho trước nào đó.

Yêu cầu: Hãy đếm xem trong dãy số \(A\) có bao nhiêu cặp số (\(A_i;A_j\)) tương đồng với \(x\) (có nghĩa là \(A_i+ A_j=x\)) với \(i<j\).

Input

• Dòng đầu tiên chứa dãy số \(n,x\) (\(n≤10^5,x≤10^6\)).
• Dòng thứ 2 chứa \(n\) phần tử của dãy số \(A\) (\(A_i≤10^9\)).

Output

• Ghi ra một số nguyên là cặp đôi tương đồng của dãy số.

Example

7 6
1 2 4 3 4 5 3 

4

Cho 2 xâu kí tự \(S\) và \(P\) có cùng độ dài là \(L\) (\(1 < L < 256\)). Hai kí tự \(S[i]\) và \(P[j]\)
được gọi là cặp kí tự đối xứng nếu chúng thỏa mãn điều kiện: \(S[i] = P[j]\) và \(i+j–1 = L\).

Yêu cầu: Xác định có bao nhiêu cặp kí tự đối xứng của 2 xâu \(S\) và \(P\).

Input

• Dòng thứ nhất chứa xâu kí tự \(S\).
• Dòng thứ nhất chứa xâu kí tự \(P\).

Output

• In ra màn hình số cặp kí tự đối xứng đã nêu trên.

Example

abmdegs
hfemfba 

3

Một phân số được gọi là phân số tối giản nếu ước chung lớn nhất của tử số và mẫu số bằng 1.

Yêu cầu: Cho trước một số nguyên dương \(N\). Hãy đếm xem có bao nhiêu phân số dương bé hơn 1, có mẫu là \(N\) và là phân số tối giản.

Input

• Chứa một số nguyên dương \(N\) (\(N ≤ 10^{16}\)).

Ouput

• Ghi ra số nguyên \(M\) là số lượng phân số theo yêu cầu trên

Example

9 

6

Nguồn: TS10LQD 2019

Cho một dãy số {An} được xác định bởi công thức truy hồi sau:
\(A_1 = 1; A_2 = 3; A_n = 2 \times A_{n-1} – A_{n-2} + 2\) với mọi n là số nguyên, \(n ≥ 3\).

Theo công thức trên, ta có dãy số:
\(A_1 = 1; A_2 = 3; A_3 = 7; A_4 = 13; A_5 = 21; ...\)

Yêu cầu: Cho trước số nguyên dương \(n\). Hãy tìm số nguyên dương \(k\) sao cho \(A_k = A_n \times A_{n+1}.\)

Input

• Một dòng duy nhất chứa số nguyên dương \(n \ (1 < n < 10^9)\).

Output

• Ghi ra số \(k\) theo yêu cầu trên.

Example

3 

10

Trên mặt phàng tọa độ \(Oxy\), cho 2 điểm \(A(m;n)\) và \(B(p;q)\). Vẽ đoạn thẳng \(AB\).

Yêu cầu: Hãy xác định có bao nhiêu điểm có hoành độ và tung độ là các số nguyên dương thuộc đoạn thẳng \(AB\) (không kể 2 mút của đoạn thẳng \(AB\)).

Dữ liệu

• Một dòng chứa 4 số nguyên dương \(m, n, p, q\) nằm trên một dòng (\(m < p; n > q\)) mỗi số cách nhau 1 dấu cách. Trong đó \(m\) và \(n\) lần lượt là hoành độ và tung độ của điểm \(A\); \(p\) và \(q\) lần lượt là hoành độ và tung độ của điểm \(B\).

Kết quả:

• Ghi ra một số \(k\) là số các điểm có tọa độ là các số nguyên dương theo yêu cầu trên.

Sample input

1 6 7 3

Sample output

2

Sample input

2 8 4 1

Sample output

0

Giới hạn: \(m, n, p, q < 10^9\)

Nguồn: TS10LQD 2020

Cho một sô nguyên dương \(k\) và một xâu ký tự \(S\). Xâu \(S\) chỉ gồm các ký tự là các chữ cái la tinh thường a..z và các chữ số 0..9, trong đó có ít nhất \(k\) ký tự là chữ số.

Yêu cầu Loại bỏ một số ký tự ra khỏi xâu \(S\) sao cho \(k\) ký tự còn lại theo đúng thứ tự đó tạo nên số nhỏ nhất. Trong \(k\) ký tự còn lại có thể cho phép các chữ số 0 đứng đầu.

Dữ liệu

• Dòng thứ nhất chứa số nguyên dương \(k\) (\(k < 10\)).
• Dòng thứ hai chứa xâu \(S\) có độ dài nhỏ hơn 250.

Kết quả

• Ghi ra gồm \(k\) ký lự còn lại của xâu \(S\) tạo nên số nhỏ nhất theo yêu câu trên.

Sample input

4
307uv5x1y08mnp

Sample output

0108

Nguồn: TS10LQD 2020

Cho \(N\) là một số nguyên dương lớn hơn 2. Xét tích \(T = 1 \cdot 2 \cdot 3 \cdot \dots \cdot N\).

Yêu cầu

• Trong các ước có dạng \(2^k\) (\(k \in \mathbb{N}\)) của số \(T\), hãy tìm số mũ \(k\) lớn nhất.

Input

• Một dòng chứa một số nguyên dương \(N\) (\(N < 10^8\)).

Output

• Ghi ra số \(k\) theo yêu cầu trên.

Example

6

4

Nguồn: TS10LQD 2020

Bài 1. Tổng Bội

Bài 2. Chia xâu đối xứng

Bài 3. VUONGTD

Bài 4. Biểu thức