Bài tập

Một cách phân tích số nguyên dương \(N\) là viết \(N\) thành tổng của một hoặc nhiều số nguyên dương, trong đó thứ tự các số hạng không quan trọng (ví dụ \(1+2+3\) và \(3+2+1\) chỉ là một cách). Để thống nhất, mỗi cách được viết với các số hạng sắp không giảm từ trái sang phải. Ví dụ \(N = 4\) có các cách: \(1+1+1+1\), \(1+1+2\), \(1+3\), \(2+2\) và \(4\).

Hãy liệt kê tất cả các cách phân tích \(N\).

Input

Một số nguyên dương \(N\) duy nhất.

Output

Mỗi dòng in một cách phân tích theo dạng N = a1+a2+...+ak (có khoảng trắng hai bên dấu =, không có khoảng trắng quanh dấu +), với \(a_1 \le a_2 \le \dots \le a_k\). Các dòng được in theo thứ tự từ điển tăng dần của dãy số hạng \((a_1, a_2, \dots, a_k)\) (so sánh số hạng đầu tiên khác nhau; do các dãy đều có tổng bằng \(N\) nên không có dãy nào là tiền tố của dãy khác).

Constraints

• \(1 \le N \le 30\)

Sample Input 1

3

Sample Output 1

3 = 1+1+1
3 = 1+2
3 = 3

Sample Input 2

6

Sample Output 2

6 = 1+1+1+1+1+1
6 = 1+1+1+1+2
6 = 1+1+1+3
6 = 1+1+2+2
6 = 1+1+4
6 = 1+2+3
6 = 1+5
6 = 2+2+2
6 = 2+4
6 = 3+3
6 = 6

Một nhân vật trong trò chơi có chỉ số máu \(H\) và giáp \(A\). Nhân vật luôn ở một trong ba vùng: Không khí, Nước hoặc Lửa. Sau mỗi bước, nhân vật bắt buộc phải chuyển sang một vùng khác với vùng hiện tại (ở bước đầu tiên có thể chọn bất kỳ vùng nào trong ba vùng). Khi bước vào một vùng, chỉ số thay đổi như sau:

Nếu sau một bước mà máu hoặc giáp \(\le 0\) thì nhân vật chết ngay và bước đó không được tính. Hãy tìm số bước nhiều nhất mà nhân vật có thể thực hiện mà vẫn còn sống.

Input

• Dòng đầu chứa số nguyên \(t\) là số bộ test.
• Mỗi bộ test là một dòng chứa hai số nguyên dương \(H\) và \(A\) là máu và giáp ban đầu.

Output

Với mỗi bộ test in ra một dòng là số bước sống sót lớn nhất.

Constraints

• \(1 \le t \le 10\)
• \(1 \le H, A \le 1000\)

Sample Input

3
5 5
25 14
30 40

Sample Output

1
7
13

Explanation

Với \((H, A) = (5, 5)\): bước đầu vào Không khí được \((8, 7)\); sau đó vào Nước sẽ có giáp \(-3\), vào Lửa sẽ có máu \(-12\), đều chết, nên đáp án là \(1\). Bước đầu vào Nước hoặc Lửa thì chết ngay.

Cho ba số nguyên \(x, y, z\). Hãy tìm và in ra số nhỏ nhất trong ba số đó.

Gợi ý: nên viết một chương trình con (hàm) nhận vào ba số và trả về giá trị nhỏ nhất, sau đó gọi hàm này trong chương trình chính.

Input

• Một dòng gồm ba số nguyên \(x, y, z\) cách nhau bởi dấu cách.

Output

• In ra một số nguyên duy nhất: giá trị nhỏ nhất trong ba số.

Constraints

• \(|x|, |y|, |z| \le 9 \cdot 10^{18}\)

Sample Input 1

7 -3 5

Sample Output 1

-3

Sample Input 2

10 10 12

Sample Output 2

10

Cho số nguyên dương \(n\). Hãy liệt kê các xâu nhị phân có độ dài đúng \(n\) mà đoạn con 01 (hai ký tự liên tiếp là 0 rồi 1) xuất hiện không quá một lần.

Input

• Một số nguyên dương \(n\).

Output

• Dòng đầu: số \(m\) là số xâu tìm được.
• \(m\) dòng sau: mỗi dòng một xâu, theo thứ tự từ điển tăng dần.

Constraints

• \(1 \le n \le 25\)

Sample Input

4

Sample Output

15
0000
0001
0010
0011
0100
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

Explanation

Xâu duy nhất bị loại là 0101, vì chứa 01 hai lần.