[🍜 Phở Cup] Round June

Tade và Tade2 là hai anh em. Năm nay, Tade lên \(A\) tuổi và Tade2 lên \(B\) tuổi. Hỏi, sau bao nhiêu năm thì số tuổi của Tade2 bằng một nửa số tuổi của Tade? Nếu điều này không thể xảy ra, in ra NO.

Input

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

Output

• Ghi ra kết quả của bài toán. Nếu không có số năm thỏa mãn, in ra NO.

Scoring

• Subtask \(1\) \((60\%\) số điểm\()\): \(A, B \le 10^3\).
• Subtask \(2\) \((40\%\) số điểm\()\): Không có ràng buộc gì thêm.

Example

9 1

7

4 2

0

8 10

NO

Tade vừa nhận việc tại Khách sạn Hilbert, đảm nhận việc vận chuyển hành lý giữa vô hạn các căn phòng và vô hạn các tầng của khách sạn. Một ngày nọ, khi đang đi giao hành lý, Tade bước vào thang máy để di chuyển giữa các tầng. Không may, ngay khi cửa đóng lại, hệ thống điều khiển gặp sự cố. Thay vì nhận lệnh từ người dùng, chiếc thang máy bắt đầu tự di chuyển theo một quy luật kỳ lạ:

Ban đầu, thang máy đứng ở tầng \(0\). Ở bước thứ \(i\) \((i \ge 1)\), thang máy sẽ cố gắng đi xuống \(i\) tầng, nếu tầng đó âm hoặc thang máy đã từng ghé qua tầng đó trước đây thì thang máy sẽ đổi ý và đi lên \(i\) tầng (dữ liệu đảm bảo thang máy sẽ không bao giờ đi lên tầng đã đi qua).

Lo lắng không biết mình sẽ bị đưa tới đâu, Tade muốn biết sau đúng \(n\) bước di chuyển, thang máy sẽ dừng ở tầng nào.

Input

• Một số nguyên không âm \(n\) \((1 \le n \le 3 \times 10^5)\).
• Dữ liệu đảm bảo thang máy không đi quá tầng thứ \(2 \times 10^6\).

Output

• In ra số tầng mà thang máy đứng tại sau \(n\) bước.

Example

6

13

Cho một chuỗi nhị phân \(s\). Hãy cắt \(s\) thành ít đoạn nhất sao cho sau khi cắt, các đoạn có thể nối lại với nhau (theo thứ tự nào đó) để tạo ra một chuỗi nhị phân đã được sắp xếp.

Lưu ý:

• Mỗi ký tự phải thuộc đúng một đoạn.
• Mỗi đoạn phải là một đoạn con liên tiếp của chuỗi ban đầu.
• Phải sử dụng tất cả các đoạn khi nối chúng lại với nhau.

Một chuỗi nhị phân là chuỗi chỉ gồm hai ký tự 0 và 1. Một chuỗi nhị phân đã được sắp xếp là chuỗi mà mọi ký tự 0 đều đứng trước mọi ký tự 1.

Input

• Dòng đầu tiên chứa một số nguyên duy nhất \(t\) (\(1 \leq t \leq 500\)) — số lượng bộ test.
• Dòng duy nhất của mỗi bộ test chứa một chuỗi \(s\) (\(1 \leq |s| \leq 500\)) bao gồm các ký tự 0 và 1, trong đó \(|s|\) biểu thị độ dài của chuỗi \(s\).

Output

• Với mỗi bộ test, in ra một số nguyên duy nhất — số lượng đoạn ít nhất cần thiết để có thể sắp xếp lại chuỗi thành một chuỗi nhị phân đã được sắp xếp.

Scoring

• Subtask \(1\) \((10\%)\): Chuỗi chỉ toàn 0 hoặc toàn 1.
• Subtask \(2\) \((20\%)\): Chuỗi đã được sắp xếp.
• Subtask \(3\) \((30\%)\): Chuỗi chỉ có đúng 2 khối liên tiếp (Ví dụ: 111000 hoặc 000111).
• Subtask \(4\) \((40\%)\): Không có ràng buộc gì thêm.

Example

6
11010
00000000
1
10
0001111
0110

3
1
1
2
1
2

Tade có một xâu \(s\) bao gồm các chữ cái Latinh viết thường. Anh ấy quyết định xóa hai ký tự liên tiếp khỏi xâu \(s\) và thắc mắc có bao nhiêu xâu khác nhau có thể nhận được sau thao tác đó.

Ví dụ, Tade có xâu aaabcc. Tade có thể nhận được các xâu khác nhau sau: abcc (bằng cách xóa hai ký tự đầu tiên hoặc ký tự thứ hai và thứ ba), aacc (bằng cách xóa ký tự thứ ba và thứ tư), aaac (bằng cách xóa ký tự thứ tư và thứ năm) và aaab (bằng cách xóa hai ký tự cuối cùng).

Input

• Dòng đầu tiên chứa một số nguyên \(t\) (\(1 \le t \le 10^4\)) — số lượng bộ test.
• Các dòng tiếp theo mô tả các bộ test:
  • Dòng đầu tiên của mỗi bộ test chứa một số nguyên \(n\) (\(3 \le n \le 2 \cdot 10^5\)).
  • Dòng thứ hai của mỗi bộ test chứa một xâu \(s\) có độ dài \(n\) bao gồm các chữ cái Latinh viết thường.
• Đảm bảo rằng tổng của \(n\) trên tất cả các bộ test không vượt quá \(2 \cdot 10^5\).

Output

• Với mỗi bộ test, in ra một số nguyên duy nhất — số lượng xâu phân biệt có thể nhận được bằng cách xóa hai chữ cái liên tiếp.

Scoring

• Subtask \(1\) \((10\%)\): \(n \le 10\).
• Subtask \(2\) \((10\%)\): Hai ký tự liên tiếp luôn bằng nhau.
• Subtask \(3\) \((30\%)\): Các ký tự ở vị trí lẻ luôn bằng nhau.
• Subtask \(4\) \((50\%)\): Không có ràng buộc gì thêm.

Example

7
6
aaabcc
10
aaaaaaaaaa
6
abcdef
7
abacaba
6
cccfff
4
abba
5
ababa

4
1
5
3
3
3
1