LearnToCP
Sign in
Navigation
HomeRoadmapProblemsAbout Us
Theory
Contest Knowledge
Selecting an IDEInteractive TasksOutput-Only Tasks
Basics
Your First ProgramData types and IOC++ syntaxModuloFunctionsVectorsMatricesTime Complexity
Sorting
SortingCounting sortRadix Sort
Optimization Techniques
Two PointersSum of numbers 1 to nPrefix sumBinary SearchGreedyBinary Search FunctionsBinary Search by AnswerDivide and Conquer
Binary Numbers
Binary NumbersNumbers in codeBitwise OperationsBitmasks
Math
Binary ExponentiationPrime NumbersPrime FactorizationGCD and LCMSieve of EratosthenesModified Sieve
Data Structures
StringsStackQueueMapsSetsPriority QueueCustom Criteria for FunctionsSegment TreesFenwick TreesSparse TablesUnion FindSqrt Decomposition
Combinatorics
Addition RuleMultiplication RuleCombinatoric ObjectsInclusion Exclusion Principle
Geometry
Geometry BasicsCross and Dot ProductLinesPolygonsPoints and PolygonsConvex Hull
Recursion
PointersRecursionGenerating Combinatoric Objects
Dynamic Programming
About DPDP problemsTree DPBitmask DP
Graph Theory
GraphsDFS and BFSShortest PathsTreesTopological SortingDijkstra's AlgorithmMinimum Spanning TreesShortest Path Algorithms
Advanced Graph Theory
BiconnectivityStrongly Connected ComponentsBipartite GraphGraph FlowAugmenting PathsFlow - Minimum Cut DualityHeavy-Light DecompositionCentroid Decomposition
Advanced Data Structures
2D and 3D Segment TreesLazy PropagationImplicit Segment TreesPersistent Segment TreesLowest Common AncestorTrieBalanced Binary Search TreesMo's Algorithm

Smallest XOR Sum

Super EasyProblem #35
Time LimitMemoryInputOutput
1 s64 MBstdinstdout

Look at the two numbers one bit at a time - the choice for each bit is independent of all the others.

A base station controls two robots. The first robot carries the number a, the second one carries the number b.

Before they start working, the station broadcasts a key - a single non-negative integer x that both robots receive. A robot then spends energy equal to its own number XOR the key, so together the two robots spend

(a⊕x)+(b⊕x)

where ⊕ denotes the bitwise XOR operation.

The station picks the key, and it can be any non-negative integer. Choose it so that the total spent energy is as small as possible, and print that smallest total.

Input

First line of input will be a single integer t - the number of testcases.
Each of the next t lines contains two integers a and b - the numbers the two robots carry.

Output

For every testcase print a single line with the smallest possible total energy.

Example

Input
3
6 12
4 9
5 5
Output
10
13
0

In the first testcase the key x=4 gives (6⊕4)+(12⊕4)=2+8=10, and no other key does better. In the third testcase both robots carry the same number, so the key x=5 empties them both.

Constraints

1≤t≤1000
1≤a,b≤109

This problem was adapted from XORwice, problem A of Codeforces Round 676 (Div. 2).

Submit your solution

Sign in to submit your solution and track your progress.

Sign in to submit