Hãy đếm số bit 1 trong biểu diễn nhị phân của các số nguyên từ 1 đến n.

Ví dụ với n = 6 thì các biểu diễn nhị phân của 1…6 là 1, 10, 11, 100, 101 và 110, do đó có tổng cộng 9 bit 1.

Ràng buộc:

• Có 50% số test của bài có n ≤ 1000.
• Có 50% số test còn lại của bài có n ≤ 10^12.

Ví dụ:

Input

6

Output

9

Link đề bài

Số đặc biệt là số nguyên có đúng 4 ước nguyên dương.

Yêu cầu: Cho trước số nguyên dương n, hãy tìm số đặc biệt bé nhất không nhỏ hơn n.

Ràng buộc:

• Có 40% số test của bài có n ≤ 1000.
• Có 60% số test còn lại của bài có n ≤ 10^9.

Ví dụ

Input

5

Output

6

Ví dụ 2

Input

15

Output

15

Link đề (dự phòng)

Một Robot di chuyển trên mặt phẳng tọa độ, bắt đầu tại điểm (0,0) và thực hiện n lệnh. Mỗi lệnh sẽ di chuyển robot lên, xuống, sang trái hoặc phải một khoảng cách. Robot sẽ dừng lại khi thực hiện xong tất cả các lệnh hoặc ngay khi quay trở lại điểm mà nó đã đi qua. Mỗi hướng được mã hóa bởi một trong 4 kí tự: U (lên), D (xuống), L (trái) hoặc R (phải).

Yêu cầu: Hãy tính tổng quãng đường mà robot di chuyển được.

Dữ liệu:

Dòng đầu tiên có số nguyên n là số lượng lệnh.

Trên n dòng tiếp theo lần lượt ghi mô tả các lệnh: Mỗi dòng có một ký tự d và một số nguyên x với ý nghĩa robot di chuyển quãng đường x về hướng d.

Kết quả: Ghi ra quãng đường robot di chuyển.

Ràng buộc:

• Có 40% số test của bài có 1≤n≤10^3, 1≤x≤10^3
• Có 60% số test còn lại của bài có 1≤n≤10^5, 1≤x≤10^6

Ví dụ

Input

3
U 2
R 3
D 1

Output

6

Xem đề

Cho ma trận bit gồm n dòng và m cột là mã hóa của một bức ảnh: mỗi bit 1 và 0 là mã hóa cho một điểm ảnh đen và trắng tương ứng của bức ảnh. Hình vuông đặc biệt trên bức ảnh là một dạng hình vuông đạt 05 tiêu chí sau:

1. Cạnh của hình chỉ gồm các điểm ảnh đen
2. Cạnh của hình song song với cạnh của bức ảnh.
3. Độ dày các cạnh của hình ở mọi vị trí trên cạnh là như nhau
4. Bên trong hình phải có ít nhất một điểm ảnh trắng, điều này nhằm đảm bảo rằng nó không phải là một hình vuông đặc.
5. Biên của cạnh hình vuông chỉ tiếp xúc với điểm ảnh trắng hoặc là biên của bức ảnh. Yêu cầu: Hãy đếm số lượng hình vuông đặc biệt tối tiểu trên ma trận mã hóa của một bức ảnh cho trước. Hình vuông đặc biệt tối tiểu là hình vuông đặc biệt không chứa bất kỳ hình vuông đặc biệt nào khác.

Dữ liệu: dòng đầu chứa hai số n, m; trên n dòng sau mỗi dòng có m số 0 hoặc 1 là giá trị bit mã hóa của điểm ảnh trắng hoặc đen tương ứng của bức ảnh.

Kết quả: Ghi ra một số là số lượng hình vuông đặc biệt tối tiểu đếm được.

Ràng buộc:

• Có 50% số test của bài có 3 ≤ n, m ≤ 50;
• Có 50% số test còn lại của bài có 3 ≤ n, m ≤ 500.

Ví dụ: Dạng hình vuông trong bộ test thứ nhất bên trái vi phạm tiêu chí 3. Bộ test thứ 2 bên phải có chứa 3 dạng hình vuông, nhưng chỉ có 2 hình vuông đặc biệt tối tiểu vì dạng hình vuông thứ 3 ở góc dưới bên phải vi phạm tiêu chí 4.

Ví dụ

Input

5 6
0 1 1 1 1 1
0 1 1 0 0 1
0 1 1 0 0 1
0 1 1 0 0 1
0 1 1 1 1 1

Output

0

Xem đề