A and B

Đề bài

Bạn có hai số nguyên a và b.

Bạn có thể thực hiện các thao tác sau:

• Ở lần thao tác thứ 1, chọn một trong hai số và tăng nó thêm 1.
• Ở lần thao tác thứ 2, chọn một trong hai số và tăng nó thêm 2.
• ...
• Ở lần thao tác thứ i, chọn một trong hai số và tăng nó thêm i.

Bạn được quyền tự chọn số lượng thao tác cần thực hiện.

Ví dụ, nếu a = 1, b = 3, ta có thể thực hiện 3 thao tác:

1. Cộng 1 vào a → a = 2, b = 3
2. Cộng 2 vào b → a = 2, b = 5
3. Cộng 3 vào a → a = 5, b = 5

Yêu cầu

Hãy tính số thao tác nhỏ nhất cần thực hiện để hai số a và b trở nên bằng nhau.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên t (1 ≤ t ≤ 100) --- số lượng bộ dữ liệu.
• Mỗi bộ dữ liệu gồm một dòng chứa hai số nguyên a và b (1 ≤ a, b ≤ 10^9).

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên là số thao tác nhỏ nhất cần thực hiện để hai số a và b bằng nhau.

Ví dụ

Input

3
1 3
11 11
30 20

Output

3
0
4

Giải thích

• Bộ dữ liệu 1: Thực hiện đúng chuỗi thao tác trong ví dụ của đề bài để thu được a = b = 5.
• Bộ dữ liệu 2: Hai số đã bằng nhau ngay từ đầu nên đáp án là 0.
• Bộ dữ liệu 3: Thực hiện 4 thao tác đầu tiên đều trên số b:

20 + 1 + 2 + 3 + 4 = 30

Khi đó b trở thành 30, bằng với a.

Trò chơi tính toán

Đề bài

Một lớp học gồm n bạn, được đánh số từ 1 đến n.

Ban đầu, bạn thứ i ghi nhớ số i.

Có k lượt chơi. Sau mỗi lượt, mỗi bạn thay số đang ghi nhớ bằng bình phương của số đó.

Sau k lượt, gọi:

S là tổng tất cả các số mà các bạn đang ghi nhớ.

Hãy tìm chữ số hàng đơn vị của S.

Input

Một dòng chứa hai số nguyên dương: k n

Output

In ra chữ số hàng đơn vị của S.

Ví dụ

Input

1 3

Output

4

Giải thích:

• Ban đầu các bạn ghi nhớ: 1, 2, 3
• Sau 1 lượt: 1, 4, 9 Tổng: 14

Chữ số hàng đơn vị là 4.

Ràng buộc

• n ≤ 10^18
• k ≤ 10^18

Xâu Bất Đối Xứng

Bạn đã biết về "xâu đối xứng" rồi đúng không? Vậy hôm nay chúng ta sẽ định nghĩa về "xâu bất đối xứng" nhé.

Bạn được cho một xâu s gồm toàn các chữ cái in thường. Trong một thao tác, bạn được phép hoán đổi vị trí của hai kí tự bất kì của xâu s.

Một xâu s độ dài n được gọi là xâu bất đối xứng khi với mọi i (1 ≤ i ≤ n), ta có:

s[i] ≠ s[n - i + 1]

Ví dụ, xâu string, dukkichi là "xâu bất đối xứng", nhưng xâu abacaba, aba, abcbd thì không phải.

Hãy xác định số thao tác nhỏ nhất cần thực hiện để biến xâu s thành một "xâu bất đối xứng"; nếu không làm được thì đưa ra -1.

Input

• Dòng thứ nhất chứa một số nguyên dương n (1 ≤ n ≤ 2 × 10^5) – độ dài xâu s.
• Dòng thứ hai chứa xâu s độ dài n chỉ chứa các ký tự latin in thường.

Output

• Đưa ra một dòng là một số nguyên duy nhất thỏa mãn điều kiện đề bài; nếu không làm được thì đưa ra -1.

Scoring

• Subtask 1 (30% số điểm): n ≤ 10^3.
• Subtask 2 (30% số điểm): xâu s chỉ gồm hai loại kí tự.
• Subtask 3 (40% số điểm): không có ràng buộc gì thêm.

Example

Input

6
string

Output

0

Chèn Một Chữ Số Để Chia Hết Cho 3

Mô tả

Cho một số tự nhiên n.

Bạn được phép chèn đúng 1 chữ số vào số n để tạo ra số chia hết cho 3 bé nhất có thể.

Lưu ý: Bạn không được sắp xếp lại các chữ số của số n.

Dữ liệu vào

Gồm một số tự nhiên:

n

Ràng buộc:

0 ≤ n ≤ 10^100000

Dữ liệu ra

In ra:

Số bé nhất chia hết cho 3 có thể tạo ra từ số n bằng cách chèn đúng 1 chữ số vào số n.

Ví dụ 1

Input

13

Output

123

Giải thích

Tổng các chữ số của 13 là:

1 + 3 = 4

Cần chèn thêm chữ số 2 để tổng chia hết cho 3:

4 + 2 = 6

Các cách chèn:

213
123
132

Số nhỏ nhất là:

123

Ví dụ 2

Input

10

Output

102

Giải thích

Tổng các chữ số của 10 là:

1 + 0 = 1

Cần chèn thêm chữ số 2 để tổng chia hết cho 3:

1 + 2 = 3

Các cách chèn:

210
120
102

Số nhỏ nhất là:

102

TỔNG CHỮ SỐ CÁC SỐ CHIA HẾT CHO K

Đề bài

Dan rất yêu thích số học và thường tự thử thách bản thân bằng những bài toán tự nghĩ ra.

Một bài toán mà Dan nghĩ ra như sau:

Cho hai số nguyên dương:

n và k

Cần tính tổng các chữ số của tất cả các số tự nhiên:

không vượt quá n

và:

chia hết cho k

Đầu vào

Gồm 2 dòng, mỗi dòng chứa hai số nguyên dương:

n k

với điều kiện:

k ≤ n

Mỗi dòng là một bộ dữ liệu cần tính riêng.

Đầu ra

In ra 2 dòng, mỗi dòng chứa một số nguyên:

là tổng các chữ số của các số tự nhiên không vượt quá n và chia hết cho k tương ứng với từng bộ dữ liệu đầu vào.

Scoring

Subtask 1 (30% số điểm)

n ≤ 10^6

Subtask 2 (30% số điểm)

n = 10^x
1 ≤ x ≤ 12

Subtask 3 (40% số điểm)

n ≤ 10^12

Ví dụ

Input

5 2
25 10

Output

6
3

Giải thích

Bộ dữ liệu 1

n = 5
k = 2

Các số chia hết cho 2 không vượt quá 5:

2, 4

Tổng chữ số:

2 + 4 = 6

Bộ dữ liệu 2

n = 25
k = 10

Các số chia hết cho 10 không vượt quá 25:

10, 20

Tổng chữ số:

1 + 0 + 2 + 0 = 3

Dãy Số Không Chứa Chữ Số A

Đề bài

Nhập số tự nhiên N và chữ số A.

Xét dãy các số tự nhiên không chứa chữ số A trong biểu diễn thập phân.

Hãy tìm số tự nhiên thứ N trong dãy đó.

Input

Gồm 2 dòng:

• Dòng thứ nhất chứa số nguyên dương N
• Dòng thứ hai chứa chữ số A

Ràng buộc:

1 ≤ N ≤ 1 000 000 000 000 000
0 ≤ A ≤ 9

Output

In ra số tự nhiên thứ N trong dãy các số không chứa chữ số A.

Ví dụ 1

Input

21
2

Output

33

Giải thích

Các số đầu tiên không chứa chữ số 2:

0, 1, 3, 4, 5, 6, 7, 8, 9,
10, 11, 13, 14, 15, 16, 17, 18, 19,
30, 31, 33, ...

Số thứ 21 là:

33

Ví dụ 2

Input

89
7

Output

108

Con Lắc Số

Một dãy con lắc được tạo ra từ một số nguyên dương N theo quy luật:

• Dãy đầu tiên: từ 1 đến N
• Sau đó: từ N-1 về 2
• Tiếp theo: từ 3 đến N-2
• Tiếp tục như vậy cho đến khi không còn số nào để tạo thành dãy mới

Ví dụ:

Với N = 6, dãy con lắc là:

1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 3, 4

Yêu cầu

Tính tổng các phần tử xuất hiện trong dãy con lắc trên, sau đó lấy phần dư chia cho 100.

Dữ liệu nhập

Một dòng duy nhất chứa một số nguyên N (1 ≤ N ≤ 10^8).

Kết quả

Một dòng duy nhất là phần dư khi tổng chia cho 100.

Ví dụ

Input:
6

Output:
42

Giải thích:
Dãy: 1 2 3 4 5 6 → 5 4 3 2 → 3 4 → tổng = 42. Kết quả: 42 mod 100 = 42

Đề bài: Tạo hình vuông từ các cột hình vuông cơ bản

Bối cảnh

Bố tặng Dino rất nhiều khối hình vuông cơ bản kích thước 1 × 1.
Hiện Dino đang xếp được 4 cột liên tiếp, mỗi cột gồm a, b, c, d hình vuông cơ bản chồng lên nhau.

Hỏi cần xếp thêm ít nhất bao nhiêu hình vuông cơ bản nữa vào các khối đã xếp để tạo thành một hình vuông?

Yêu cầu

Tìm số lượng tối thiểu hình vuông cơ bản cần thêm vào để tạo thành một hình vuông.

Dữ liệu nhập vào từ bàn phím

• Gồm 4 dòng, mỗi dòng chứa một số nguyên dương: a, b, c, d
  (1 ≤ a, b, c, d ≤ 100)

Kết quả ghi ra màn hình

• Một số tự nhiên là số hình vuông cơ bản cần thêm.

Ví dụ