Bạn được cho ba số nguyên ~a, b, c~ trong đó chỉ có hai số có giá trị bằng nhau.

Yêu cầu: Tìm số có giá trị khác với hai số còn lại.

Dữ liệu vào:

• Dòng đầu tiên chứa một số nguyên ~t\ (1\leq t\leq 90)~.
• Dòng tiếp theo chứa ba số nguyên ~a, b, c\ (0\leq a, b, c\leq 9)~.

Dữ liệu ra:

• In ra mỗi dòng chứa một số nguyên là kết quả của test tương ứng.

Input:

10
1 2 2
4 3 4
5 5 6
7 8 8
9 0 9
3 6 3
2 8 2
5 7 7
7 7 5
5 7 5

Output:

1
3
6
7
0
6
8
5
5
7

Bạn là người yêu thích vi khuẩn. Bạn muốn nuôi chúng trong một cái hộp.

Ban đầu cái hộp rỗng. Mỗi sáng, bạn có thể cho số lượng vi khuẩn tùy ý vào hộp. Mỗi đêm, mỗi con vi khuẩn trong hộp sẽ phân chia thành hai con vi khuẩn. Bạn muốn có chính xác ~x~ vi khuẩn trong hộp vào một ngày nào đó.

Yêu cầu: Hãy cho biết số vi khuẩn tối thiểu bạn cần cho vào hộp trong những ngày nuôi chúng là bao nhiêu?

Dữ liệu vào:

• Một dòng duy nhất chứa một số nguyên ~x\ (1\leq x\leq 10^9)~.

Dữ liệu ra:

• In ra một dòng chứa một số nguyên là câu trả lời.

Input 1:

5

Output 1:

2

Input 2:

8

Output 2:

1

Giải thích:

• Ở ví dụ thứ nhất, ngày đầu tiên ta bỏ ~1~ vi khuẩn vào hộp và sáng ngày thứ ba sẽ có ~4~ vi khuẩn trong hộp. Bây giờ ta bỏ thêm ~1~ vi khuẩn nữa vào hộp sẽ có được ~5~ vi khuẩn trong hộp. Tóm lại ta đã bỏ ~2~ vi khuẩn vào nên câu trả lời là ~2~.
• Ở ví dụ thứ hai, ngày đầu tiên ta bỏ ~1~ vi khuẩn vào hộp và ngày thứ tư ta sẽ có ~8~ vi khuẩn trong hộp. Vì vậy câu trả là ~1~.

Cho số nguyên dương ~n~. Liệt kê tất cả các xâu nhị phân độ dài ~n~ (gồm cả các xâu có số ~0~ đứng đầu).

Dữ liệu vào:

• Một dòng duy nhất chứa số nguyên dương ~n~.

Dữ liệu ra:

• Gồm nhiều dòng, mỗi dòng là một xâu nhị phân độ dài ~n~, các xâu được liệt kê theo thứ tự từ điển tăng dần.

Input:

3

Output:

000
001
010
011
100
101
110
111

Giới hạn:

• ~1 ≤ n ≤ 16~.

Có ~n~ quả táo biết cân nặng của từng quả là ~a_1, a_2, \dots, a_n~.

Yêu cầu: Hãy chia những quả táo thành hai nhóm sao cho chênh lệch tổng cân nặng của chúng nhỏ nhất.

Dữ liệu vào:

• Dòng đầu tiên chứa một số nguyên ~n\ (1\leq n\leq 20)~: số lượng quả táo
• Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n\ (1\leq a_i\leq 10^9)~: cân nặng của từng quả táo.

Dữ liệu ra:

• In ra một số nguyên: chênh lệch cân nặng nhỏ nhất của hai nhóm.

Input:

5
3 2 7 4 1

Output:

1

Giải thích:

• Nhóm 1 có quả táo nặng 2, 3 và 4 (tổng cân nặng 9), nhóm 2 có quả táo nặng 1 và 7 (tổng cân nặng 8).

Bạn được cho một mảng ~a~ có độ dài ~n~. Bạn có thể thực hiện thao tác sau nhiều lần (có thể không):

• Chọn ~i, j, b~: Hoán đổi bit thứ ~b~ trong dãy nhị phân của ~a_i~ và ~a_j~

Tìm giá trị lớn nhất của ~max(a) - min(a)~ với ~max(a)~ là phần tử lớn nhất của dãy ~a~ và ~min(a)~ là phần tử bé nhất của dãy ~a~.

Trong biểu diễn nhị phân, các bit được đánh số từ phải sang trái. Coi như có vô số bit ~0~ đứng đầu của bất kỳ biểu diễn nhị phân nào.

Ví dụ, hoán đổi bit thứ ~0~ của ~4 = 100_2~ và ~3 = 11_2~ sẽ có kết quả ~101_2 = 5~ và ~10_2 = 2~. Hoán đổi bit thứ ~2~ của ~4 = 100_2~ và ~3 = 11_2~ sẽ có kết quả ~000_2 = 0~ và ~111_2 = 7~.

Dữ liệu vào:

• Dòng thứ nhất chứa một số nguyên ~t\ (1\leq t\leq 128)~: số testcases.
• Dòng đầu tiên của mỗi test chứa một số nguyên ~n\ (3\leq n\leq 512)~: độ dài dãy ~a~.
• Dòng thứ hai của mỗi test chứa ~n~ số nguyên ~a_1, a_2,\dots, a_n\ (0\leq a_i\leq 1024)~: các phần tử dãy ~a~.

Dữ liệu đảm bảo tổng ~n~ tất cả testcases không vượt quá ~512~.

Dữ liệu ra:

• In ra mỗi dòng ứng với ~max(a) - min(a)~ lớn nhất của mỗi test.

Input:

4
3
1 0 1
4
5 5 5 5
5
1 2 3 4 5
7
20 85 100 41 76 49 36

Output:

1
0
7
125

Giải thích:

• Ở ví dụ đầu tiên, có thể chứng minh rằng ta không cần thực hiện bất kỳ thao tác nào, ~max(a) - min(a)~ lớn nhất là ~1 - 0 = 1~.
• Ở ví dụ thứ hai, không có thao tác nào có thể thay đổi mảng, ~max(a) - min(a)~ lớn nhất là ~5 - 5 = 0~.
• Ở ví dụ thứ ba, mảng ban đầu ~a = [1,2,3,4,5]~, chúng ta có thể thực hiện một thao tác ~i = 2, j = 5, b = 1~. Mảng bây giờ trở thành ~a = [1, 0, 3, 4, 7]~. Có thể chứng minh rằng bất kỳ thao tác tiếp theo cũng không dẫn đến kết quả tốt hơn, do đó đáp án là ~max(a) - min(a) = 7 - 0 = 7~.

Bạn được cho hai số nguyên ~x~ và ~y~ không âm. Xét hai dãy vô hạn ~a_1, a_2, a_3, \dots~ và ~b_1, b_2, b_3,\dots~ có

• ~a_n = n\oplus x~
• ~b_n = n\oplus y~

Ở đây, ~x\oplus y~ biểu thị phép toán bitwise XOR số nguyên ~x~ và ~y~.

Ví dụ với ~x = 6~, ~8~ phần tử đầu tiên của dãy ~a = [7,4,5,2,3,0,1,14,\dots]~. Lưu ý rằng chỉ số của dãy các phần tử bắt đầu bằng ~1~.

Nhiệm vụ của bạn là tìm dãy con chung liên tiếp dài nhất của dãy ~a~ và ~b~.

Dữ liệu vào:

• Dòng đầu tiên chứa một số nguyên ~t\ (1\leq t\leq 10^4)~ là số test.
• ~t~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x~ và ~y~ ~(0\leq x,y\leq 10^9, x\neq y)~

Dữ liệu ra:

• In ra mỗi dòng một số nguyên là độ dài dãy con chung liên tiếp dài nhất của mỗi test.

Input:

4
0 1
12 4
57 37
316560849 14570961

Output:

1
8
4
33554432

Giải thích:

• Ở test đầu tiên, ~7~ phần tử đầu tiên của dãy ~a~ và ~b~ như sau:
  • ~a = [1,2,3,4,5,6,7,\dots]~
  • ~b = [0,3,2,5,4,7,6,\dots]~

Có thể chứng minh được rằng không tồn tại số nguyên ~k~ nào sao cho dãy ~[k, k + 1]~ xuất hiện trong dãy ~b~. Vì vậy đáp án là ~1~.

• Ở test thứ ba, ~20~ phần tử đầu tiên của dãy ~a~ và ~b~ như sau:
  • ~a = [56,59,58,61,60,63,62,49,48,51,50,53,52,55,54,41,40,43,42,45,\dots]~
  • ~b = [36,39,38,33,32,35,34,45,44,47,46,41,40,43,42,53,52,55,54,49,\dots]~

Có thể chứng minh được rằng chỉ có một dãy con chung liên tiếp dài nhất là dãy ~[41, 40, 43, 42]~ có độ dài là ~4~.