Bài tập

Cô giáo đưa cho hai bạn Nam và Bình một xâu \(s\) chỉ gồm các chữ số \(0\)–\(9\) và đặt bài toán: hãy cắt xâu thành đúng \(K\) đoạn liên tiếp (mỗi đoạn không rỗng, mỗi ký tự thuộc đúng một đoạn) sao cho giá trị số của mỗi đoạn không vượt quá \(Z\). Đoạn được hiểu là số nguyên thập phân và có thể có chữ số \(0\) ở đầu (ví dụ 07 có giá trị \(7\)).

Trong tất cả các cách cắt hợp lệ, hãy chọn cách sao cho tổng giá trị của \(K\) đoạn là lớn nhất. Nếu không có cách cắt nào hợp lệ, in ra \(-1\).

Input

• Dòng đầu chứa số nguyên \(T\) là số bộ test.
• Mỗi bộ test gồm hai dòng: dòng đầu chứa hai số nguyên \(K\) và \(Z\); dòng thứ hai chứa xâu \(s\).

Output

Với mỗi bộ test in ra một dòng là tổng lớn nhất, hoặc \(-1\) nếu không thể cắt.

Constraints

• \(1 \le T \le 10\)
• \(1 \le K \le 100\), \(1 \le Z \le 10^9\)
• \(1 \le |s| \le 100\), \(s\) chỉ gồm các ký tự từ 0 đến 9

Sample Input

3
2 50
4817
1 20
123
3 100
90210

Sample Output

65
-1
111

Explanation

Bộ test 1: cắt 48|17, tổng \(65\). Bộ test 2: chỉ có thể lấy cả xâu là \(123 > 20\) nên không hợp lệ. Bộ test 3: cắt 90|21|0, tổng \(111\).

Một xâu là đối xứng (palindrome) nếu đọc từ trái sang phải hay từ phải sang trái đều cho cùng một kết quả, ví dụ madam, civic, a.

Cho xâu \(S\). Ta có thể cắt \(S\) tại một số vị trí (có thể không cắt) để chia thành các đoạn liên tiếp. Hãy liệt kê mọi cách cắt sao cho mọi đoạn thu được đều là xâu đối xứng.

Input

Một dòng duy nhất chứa xâu \(S\) gồm các chữ cái Latinh thường.

Output

In mỗi cách cắt trên một dòng: các đoạn theo thứ tự từ trái sang phải, cách nhau đúng một dấu cách. Các cách cắt được in theo thứ tự sau: so sánh hai cách cắt từ trái sang phải, đoạn đầu tiên nào ngắn hơn thì cách cắt đó đứng trước (nếu hai đoạn đầu bằng nhau thì so sánh tiếp đoạn thứ hai, v.v.).

Constraints

• \(1 \le |S| \le 30\), \(S\) gồm chữ cái thường a-z.
• Để kết quả không quá lớn, đảm bảo số cách cắt hợp lệ không vượt quá \(10^5\).

Sample Input 1

civicab

Sample Output 1

c i v i c a b
c ivi c a b
civic a b

Sample Input 2

aabaa

Sample Output 2

a a b a a
a a b aa
a aba a
aa b a a
aa b aa
aabaa

Cho một tờ giấy hình chữ nhật kích thước \(A \times B\) (đơn vị nguyên). Người ta muốn cắt hết tờ giấy thành các hình vuông bằng nhau, không được thừa mảnh nào và không được ghép lại. Hãy tìm số hình vuông ít nhất có thể cắt được.

Input

• Một dòng chứa hai số nguyên dương \(A, B\).

Output

• In ra một số nguyên duy nhất: số hình vuông ít nhất.

Constraints

• \(1 \le A, B \le 4 \cdot 10^9\)

Sample Input 1

6 9

Sample Output 1

6

Sample Input 2

5 5

Sample Output 2

1

Explanation

Ví dụ 1: cạnh hình vuông lớn nhất có thể là \(\gcd(6,9)=3\), khi đó số hình vuông là \((6/3)\cdot(9/3)=6\).

Ba số nguyên \(p, q, r\) được viết theo đúng thứ tự cho trước. Ba số này được gọi là lập thành cấp số nhân nếu số ở giữa có bình phương bằng tích của hai số còn lại, tức là \(q^2 = p \cdot r\).

Cho ba số nguyên \(p, q, r\) thỏa mãn \(p < q < r\) và cả ba đều khác \(0\). Hãy cho biết ba số đó, theo thứ tự đã cho, có lập thành cấp số nhân hay không.

Input

• Một dòng chứa ba số nguyên \(p, q, r\) cách nhau bởi dấu cách.

Output

• In ra YES nếu ba số lập thành cấp số nhân, ngược lại in ra NO.

Constraints

• \(p < q < r\)
• \(p, q, r \ne 0\)
• \(|p|, |q|, |r| \le 10^9\)

Sample Input 1

3 6 12

Sample Output 1

YES

Sample Input 2

-9 -6 -5

Sample Output 2

NO

Explanation

Ở ví dụ 1: \(6^2 = 36 = 3 \cdot 12\). Ở ví dụ 2: \((-6)^2 = 36\) nhưng \((-9)\cdot(-5) = 45\).