Phép chia (chia hết, chia dư) nâng cao

Cho một số tự nhiên \(n\). Bạn có thể đổi chỗ các chữ số của \(n\). Hãy tìm ra số lớn nhất chia hết cho \(36\) sau nhiều lần hoán đổi vị trí các chữ số của \(n\). Nếu không tìm được thì xuất -1.

Input

• Nhập vào số tự nhiên \(n\).
• Ràng buộc:
  • \(1 \le \text{len}(n) \le 10^3\)

Output

• In ra số lớn nhất chia hết cho \(36\) sau khi hoán đổi vị trí các chữ số trong \(n\). Nếu không có thì xuất -1.

Example

193

-1

810

180

Cho một số tự nhiên \(N\). Bạn được phép hoán vị (sắp xếp lại) vị trí các chữ số của \(N\) để tạo thành một số tự nhiên mới.

Yêu cầu

Hãy tìm số tự nhiên có giá trị nhỏ nhất có thể tạo thành sao cho số đó chia hết cho \(36\) và không có chữ số \(0\) vô nghĩa ở đầu. Nếu không thể tạo ra bất kỳ số nào thỏa mãn điều kiện, hãy in ra \(-1\).

Input

• Gồm một dòng duy nhất chứa số tự nhiên \(N\). Số lượng chữ số của \(N\) nằm trong khoảng từ \(1\) đến \(10^5\) chữ số.

Output

• Ghi ra một số duy nhất là kết quả của bài toán (số nhỏ nhất chia hết cho \(36\) được tạo thành). Nếu không tồn tại số thỏa mãn, in ra \(-1\).

Example

432

324

30312

10332

123

-1

Constraints

• Có \(80\%\) số test tương ứng với \(80\%\) số điểm thỏa mãn: Giá trị của \(N \leq 10^9\).
• \(20\%\) số test còn lại tương ứng với \(20\%\) số điểm không có ràng buộc gì thêm.

Cho trước số nguyên dương \(n\) và một thao tác tác \(Q\) được định nghĩa như sau:

• Chọn một chữ số bất kì từ \(n\) và xoá nó đi và nếu kết quả thu được có các số không đứng đầu thì các số \(0\) này sẽ tự động bị mất đi
  (Thao tác không thể thực hiện khi \(n\) chỉ còn một chữ số)

Nhiệm vụ của bạn là thực hiện thao tác \(Q\) lên \(n\) sao cho kết quả thu được là một số chia hết cho \(25\) và số lần xoá là ít nhất có thể và sau đó in số lần xoá ít nhất này ra màn hình.

Ví dụ 1: Giả sử ta có số \(n=71345\), thì ta lần lượt xoá đi các chữ số \(1,3,4\) khi đó kết quả thu được là số \(75\), là một số chia hết cho 25. Do đó số lần xoá ít nhất là \(3\)

Input

• Dòng đầu tiên chứa số nguyên dương \(t(1\le t\le 10000)\) - Thể hiện số testcase
• \(t\) dòng tiếp theo, mỗi dòng chứa số nguyên dương \(n(25\le n\le 10^{18})\) ( input đảm bảo rằng, \(n\) không có bất kỳ số \(0\) nào đứng đầu )

Output

• Ứng với mỗi testcase, hãy in kết quả ra màn hình.
  (Nếu không tồn tại cách xoá nào để thu được kết quả chia hết cho 25 thì in ra màn hình số 100)

Example

3
71345
100
265

3
0
1

Một số \(n\) bất kì luôn có \(1\) tập ước số không chứa \(1\) riêng của nó, dù là số nguyên tố hay hợp số. Ví dụ như số \(6\) có tập ước số không chứa \(1\) là \((2;3;6)\), còn số \(420\) có tập ước số không chứa \(1\) là \((2;3;4;5;6;7;10;12;14;15;20;21;28;35;60;84;105;140;210;420)\). Trinh mới học thêm về số nguyên tố và hợp số, liền về nhà lấy giấy ra viết \(1\) số \(420\) và dãy ước không chứa \(1\) của chính số \(420\) ấy. Viết xong rồi, cậu nhìn lại thì thắc mắc: Ủa? Sao có nhiều đoạn số liên tiếp thế này? Có đoạn có tới \(6\) số liên tiếp lận? (Nếu bạn thắc mắc là đoạn nào, thì đó là đoạn \((2;3;4;5;6;7)\) đấy) Rồi cô nghĩ tiếp: Thế nếu mình muốn tạo ra \(1\) số \(n\) bất kì mà trong dãy ước ấy có ít nhất \(1\) đoạn liên tiếp có \(k\) số thì làm thế nào nhỉ? Cô bí bài này nên cô muốn nhờ các bạn ở LQDOJ rằng: Cho \(1\) số tự nhiên \(k(k\le 100)\), hãy tìm số nguyên dương \(n\) bé nhất có thể mà trong dãy ước số không chứa \(1\) của nó có ít nhất \(1\) đoạn số liên tiếp có chiều dài không nhỏ hơn \(k\).

Input

• Duy nhất \(1\) số \(k\)

Output

• Ans mod cho \(10^9+7\).

Example

2

6

Cho hai số nguyên dương \(N\) và \(K\).

Hãy in ra một dãy số gồm \(N\) phần tử thỏa mãn các điều kiện:

• \(A_1,A_2,...,A_N\) đôi một phân biệt
• \(A_1+A_2+...+A_N\) chia hết cho \(K\)

Input

• Dòng 1: \(Q\) \((1 \le Q \le 10^2)\) - số câu hỏi
• \(Q\) dòng sau, mỗi dòng gồm hai số nguyên dương \(N\) và \(K\) không quá \(10^4\)

Output

• Ứng với mỗi test in ra đáp án thỏa mãn đề bài. Bạn có thể in ra bất kỳ đáp án hợp lệ nào.

Example

1
6 9

2 5 7 3 10 9

Đức rất thích cống. Nhận thấy sở thích này rất bất thường và không sạch sẽ, ami quyết định bày Đức một trò chơi liên quan đến số học.

ami cho Đức 4 số \(c,u,o,m\). Đức có thể chọn một trong 3 số \(u, o, m\) và chia \(c\) cho số được chọn. Đức có thể lặp lại thao tác trên với số lần vô hạn nếu cậu thích, mục tiêu là làm cho số \(c\) trở thành \(1\). Tuy không thích số học, nhưng lại không dám làm trái lời ami, Đức muốn nhờ các bạn tìm ra số thao tác ít nhất để biến \(c\) thành \(1\), hoặc báo cho Đức là không thể, để Đức còn có thời gian đi chơi với cống.

Input

• Dòng đầu tiên chứa \(t\) là số câu hỏi.
• \(t\) câu hỏi có dạng như sau: Dòng đầu tiên của mỗi câu hỏi chứa 1 số nguyên \(c\), dòng thứ hai chứa 3 số nguyên \(u, o, m\).

Output

• Với mỗi câu hỏi, hãy in ra số thao tác ít nhất cần dùng để biến \(c\) thành \(1\) hoặc in ra \(−1\) nếu không tồn tại bất kì cách làm nào.

Scoring

Trong tất cả các test, \(1 \leq c,u,o,m \leq 10^{18}\)

• Subtask \(1\) (\(40\%\) số điểm): \(t=1, u=o=m\)
• Subtask \(2\) (\(20\%\) số điểm): \(t \leq 100\), \(u,o,m\) đôi một nguyên tố cùng nhau
• Subtask \(3\) (\(20\%\) số điểm): \(t \leq 100, u=o\)
• Subtask \(4\) (\(20\%\) số điểm): \(t \leq 100\)

Example

3
6
1 2 3
7
1 2 7
8
4 4 4

2
1
-1

Cho 3 số nguyên dương \(x, y, z\). Trong đó \(1 \leq x \leq y \leq z \leq 10^4\).

Trong 1 LƯỢT, có thể +1 hoặc -1 cho 1 trong ba số \(x, y, z\).

Hãy tìm số LƯỢT ít nhất để \(1 \leq x \leq y \leq z,\ z \% y + z \% x + y \% x = 0.\) ('%' là phép chia lấy dư)

Lưu ý, trong Input dòng đầu tiên là số test, trong Output mỗi kết quả được in ra trên một hàng.

Input

2
1  1  3
3  3  5

Output

0
1

GIẢI THÍCH

• test \(1 (x = 1, y = 1, z = 3)\): vì \(z \% y + z \% x + y \% x = 0\) -> nên không cần thêm lượt nào nữa, đáp án là \(0\).
• test \(2 (x = 3, y = 3, z = 5)\): ta có thể cộng \(1\) vào \(z\) và thỏa mãn điều kiện, đáp án là \(1\).

Một số nguyên không âm \(x\) được gọi là đẹp nếu \(x\) chia hết một trong ba số \(4, 7, 11\). Hãy tìm số lượng số đẹp nằm trong khoảng \([L; R]\)

Input

• Dòng đầu chứa \(t\) không quá \(1000\) - số câu hỏi
• \(t\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(L, R\) (\(L < R\))

Output

• Kết quả thỏa mãn yêu cầu đề bài ứng với mỗi câu hỏi.

Example

2
1 10
11 15

3
3

Scoring

• \(50\%\) số test có \(0 \le L < R \le 10^6\).
• \(50\%\) số test có \(0 \le L < R \le 10^{12}\).