Khoa rất giỏi khi giải các bài toán tính tổng dãy số nhưng lập trình trên máy tính thì chưa thành thạo. Khoa muốn nhờ các bạn giúp đỡ với bài toán sau:
Cho số nguyên dương \(N\). Yêu cầu tính tổng \(N\) số lẻ đầu tiên bắt đầu từ 1.

Input

• Gồm 1 dòng duy nhất chứa số tự nhiên \(N (1 \le N \le 10^9)\)

Output

• Gồm 1 dòng duy nhất là kết quả của bài toán, sai số không quá 100.

Example

3

9

Cho một bảng hình vuông có kích thước \(n \times n\) được chia thành lưới ô vuông đơn vị, các vị trí đỉnh của các ô vuông đơn vị được gọi là các mắt lưới. Người ta muốn đếm số lượng hình vuông thỏa mãn 2 điều kiện sau:

• Mỗi cạnh hình vuông phải song song với 1 trong 2 cạnh bảng.
• Cả 4 đỉnh của hình vuông phải nằm tại vị trí của các mắt lưới

Ví dụ với hình vuông kích thước \(3 \times 3\) thì ta có \(14\) hình vuông thỏa mãn cả 2 điều kiện trên.
Cho số tự nhiên \(n\), em hãy đếm số lượng hình vuông trong bảng \(n \times n\) thỏa mãn cả hai điều kiện trên.

Input

• Gồm 1 dòng duy nhất chứa số tự nhiên \(n (1 \le n \le 10^6)\)

Output

• Số lượng hình vuông có thể tìm được, sai số không quá 100.

Example

3

14

Hint

\(14 = 3 * 3 + 2 * 2 + 1 * 1\)

Cho bảng hình vuông có kích thước \(N \times N\). Người ta điền các số từ \(1\) đến \(N \times N\) vào bảng theo chiều xoắn ốc từ ngoài vào trong, theo chiều kim đồng hồ bắt đầu từ ô góc trái trên. Hình bên dưới minh họa cho bảng kích thước \(4 \times 4\) và \(5 \times 5\).

Yêu cầu em hãy tính tổng các phần tử lớn nhất trên mỗi dòng của bảng.

Input

• Gồm 1 dòng duy nhất chứa số tự nhiên \(N (1 \le N \le 10^6)\)

Output

• Gồm 1 dòng duy nhất là kết quả của bài toán, sai số không quá 100.

Example

5

85

Nấm là một cô bé đáng yêu và tốt bụng. Cô bé đặc biệt thích truyện cổ tích. Vì thế, đêm qua, Nâm nằm mơ về nàng Lọ Lem. Trong giấc mơ, Lọ Lem không bị mụ dì ghẻ bắt phân loại các hạt đậu nữa mà bắt nhặt gạo. Có rất nhiều gạo trong kho, các hạt gạo được đánh số thứ tự là các số nguyên liên tiếp từ \(a\) đến \(b\). Mụ bắt nàng phải nhặt ra các hạt gạo mà có số chia hết cho số \(k\) cho trước. Đồng thời sau khi nhặt xong phải trả lời cho mụ biết số lượng hạt gạo nhặt được. Việc nhặt gạo thì quá đơn giản, chỉ trong tích tắc bầy chim đã giúp nàng nhặt xong. Bây giờ nhiệm vụ của Nấm là đếm số lượng hạt gạo đã nhặt được. Thật không may, chưa đếm xong thì Nấm đã tỉnh dậy
Yêu cầu em hãy trả lời giúp Nấm xem nếu hoàn thành công việc của mình thì Nấm sẽ đếm được bao nhiêu hạt gạo?

Input

Dữ liệu đầu vào từ bàn phím gồm 3 dòng

• Dòng thứ nhất chứa số tự nhiên \(b\)
• Dòng thứ hai chứa số tự nhiên \(a\)
• Dòng thứ ba chứa số tự nhiên \(k\)

\((1 \le a \le b \le 10^{18};1 \le k \le 10^{18})\)

Output

• Gồm 1 dòng duy nhất là kết quả của bài toán.

Scoring

• Subtask 1 (\(50\%\) số điểm) \(1 \le a \le b \le 10^6, 1 \le k \le 10^6\)
• Subtask 2 (\(50\%\) số điểm) Không có ràng buộc gì thêm

Example

10
3
5

2

9
6
5

0

Cho dãy số \(2, 5, 10, 17, 26...\)
Tìm số hạng thứ \(n\) của dãy số trên

Input

• Gồm 1 dòng duy nhất chứa số tự nhiên \(n (1 \le n \le 10^9)\)

Output

• Gồm 1 dòng duy nhất là kết quả của bài toán, sai số không quá 100.

Example

10

101

Có những người bạn đang chơi game trên một bộ điều khiển. Bộ điều khiển này có \(2\) cái cần điều khiển, nhưng chỉ có \(1\) bộ sạc cho \(2\) cái cần này. Cần đầu tiên được sạc ở mức \(a_1\) phần trăm và cần thứ hai thì ở mức \(a_2\) phần trăm. Bộ sạc chỉ có thể sạc cho \(1\) cái cần ở đầu của mỗi phút. Trong mỗi phút, cái cần hoặc là giảm đi \(2\) phần trăm (nếu không kết nối với bộ sạc), hoặc là được sạc lên \(1\) phần trăm (nếu kết nối với bộ sạc).

Trò chơi tiếp tục trong khi cả hai cần điều khiển đều có năng lượng ở mức dương. Do đó, nếu vào đầu mỗi phút một cái cần điều khiển được sạc \(1\) phần trăm, nó phải được kết nối với bộ sạc, nếu không trò chơi sẽ dừng lại. Nếu mức năng lượng của \(1\) cái cần về \(0\) thì trò chơi cũng sẽ dừng lại.

Xác định số phút tối đa mà trò chơi có thể kéo dài. Biết rằng trò chơi không thể bị tạm dừng, hay nói cách khác, tại mỗi thời điểm, cả hai cần điều khiển đều phải được bật. Và cả \(2\) cần điều khiển đều có thể có mức năng lượng lớn hơn \(100\) phần trăm.

Input

• Dòng 1: số nguyên dương \(T\) (\(1 \le T \le 100\)) là số bộ test.
• \(T\) dòng tiếp theo, mỗi dòng chứa hai số tự nhiên \(a_1, a_2\) (\(1 \le a_1, a_2 \le 100\)) lần lượt là mức năng lượng ban đầu của cần đầu và cần hai.

Output

• Với mỗi test, in ra số phút tối đa.

Example

2
3 5
4 4

6
5

Tuấn và Tài đang điều khiển một con robot. Mỗi người trong số họ đều có một nút điều khiển robot.

Tuấn nhấn giữ nút sau \(A\) giây kể từ khi robot khởi động, và Tuấn nhả nút sau \(B\) giây kể từ khi robot khởi động. Tài cũng nhấn giữ nút sau \(C\) giây kể từ khi robot khởi động, và Tài nhả nút sau \(D\) giây kể từ khi robot khởi động.

Aquarius hỏi rằng hai bạn cùng nhấn giữ nút trong bao nhiêu giây?

Input

• Dòng 1: Số nguyên dương \(T\) (\(1 \le T \le 100\)) là số bộ dữ liệu.
• \(T\) dòng sau, mỗi dòng gồm 4 số nguyên \(A, B, C, D\).

Output

• Với mỗi bộ dữ liệu: In ra khoảng thời gian (tính bằng giây) mà cả Tuấn và Tài đều đang nhấn giữ nút của họ.

Constraints

• \(0 \le A < B \le 10^9\)
• \(0 \le C < D \le 10^9\)

Example

3
0 75 25 100
0 33 66 99
10 90 20 80

50
0
60

Một xâu được gọi là xâu đối xứng nếu nó đọc giống nhau từ trái sang phải và từ phải sang trái. Ví dụ: abcba, abba, xyzzyx... là xâu đối xứng, abc, abab, mnnn không phải là xâu đối xứng.

Bạn được cho một xâu \(S\) bao gồm các chữ cái tiếng Anh viết thường. Mỗi lần biến đổi, bạn có thể chọn bất kỳ một vị trí nào trong xâu rồi thay đổi chữ cái ở vị trí đó thành bất kỳ chữ cái tiếng Anh viết thường nào khác và độ dài của xâu là không đổi. Bạn cũng có thể hoán vị thứ tự của các chữ cái trong xâu một cách tùy ý. Chú ý rằng hoán vị không được tính là một phép biến đổi.

Yêu cầu: Hãy tính số lần biến đổi tối thiểu để xâu \(S\) trở thành một xâu đối xứng. Nếu sau số lần biến đổi tối thiểu ấy có nhiều xâu \(S\) thỏa mãn, in ra xâu có thứ tự từ điển nhỏ nhất.

Input

• Nhập từ bàn phím xâu \(S\) bao gồm các chữ cái tiếng Anh viết thường.

Output

• In ra xâu đối xứng có thứ tự từ điển nhỏ nhất có thể nhận được sau số lần biến đổi tối thiểu.

Scoring

• Nếu chương trình chạy đúng những trường hợp \(N \leq 10\) và chỉ có \(3\) loại ký tự a, b và c, thí sinh sẽ được \(40\) điểm.
• Nếu chương trình chạy đúng những trường hợp \(N \leq 1000\), thí sinh sẽ được \(80\) điểm.
• Nếu chương trình chạy đúng những trường hợp \(N \leq 10^5\), thí sinh sẽ được \(100\) điểm.

Example

abac

abba

abacad

aabbaa

Một số tự nhiên \(X\) được gọi là số ODD đối xứng nếu như:

• Các chữ số của \(X\) đều là số lẻ.
• \(X\) đọc từ trái sang phải cho kết quả giống như đọc từ phải sang trái.

Các số ODD đối xứng đầu tiên: \(1; 3; 5; 7; 9; 11; 33; 55; 77; 99; 111; 131; \dots\)

Yêu cầu: Nhập từ bàn phím số tự nhiên \(N\). Hãy in ra số ODD đối xứng thứ \(N\).

Input

• Nhập số tự nhiên \(N\) với \(1 \le N \le 10^{16}\).

Output

• Xuất ra số ODD đối xứng thứ \(N\).

Example

2

3

7

33

Scoring

• Có \(60\%\) số test tương ứng với \(60\%\) số điểm của bài với \(N < 10^6\).
• Có \(40\%\) số test còn lại tương ứng với \(40\%\) số điểm của bài với \(N < 10^{16}\).