Ghicitoare

Cerință

Fie un număr natural nenul $n$, cunoscut. RAU-Gigel alege un număr oarecare din intervalul închis $[1,n]$, fie acesta $x$. Apoi calculează “suma XOR” S = 1 ^ 2 ^ ... ^ (x-2) ^ (x-1) ^ (x+1) ^ (x+2) ^ ... ^ n pe care v-o comunică. Puteți să-l ghiciți pe $x$? RAU-Gigel nu prea are răbdare, el vrea repede un răspuns de la voi.

Am notat cu ^ operația XOR (operatorul de disjuncție exclusivă).

Ca să fie sigur că nu nimeriți din întâmplare răspunsul, RAU-Gigel vă testează de mai multe ori.

Date de intrare

Fișierul de intrare ghicitoare.in conține pe prima linie un număr natural $T$ reprezentând numărul de teste / ghicitori pe care RAU-Gigel vi le propune, apoi $T$ linii care conțin perechi de forma n S, separate printr-un spațiu, cu semnificația de mai sus.

Date de ieșire

Fișierul de ieșire ghicitoare.out va conține $T$ rânduri, cu răspunsurile $x$, în ordinea solicitării, câte unul pe linie, la ghicitorile lui RAU-Gigel.

Restricții și precizări

• $1 \leq T \leq 10$, $1 \leq n \leq 1 \ 000 \ 000 \ 000$, $0 \leq S \leq 1 \ 000 \ 000 \ 000$, $1 \leq x \leq n$;
• Pentru teste în valoare de $10$ de puncte: $T = 2, n \leq 100$;
• Pentru teste în valoare de alte $30$ de puncte: $n \leq 1 \ 000 \ 000$;

Exemplu

ghicitoare.in

2
5 2
10 14

ghicitoare.out

3
5

Explicație

RAU-Gigel vă propune $2$ ghicitori.

La prima ghicitoare avem: $n = 5$, $S = 2$. Numărul căutat este $3$. Intr-adevăr:

S = 1 ^ 2 ^ 4 ^ 5 = 
|001| ^
|010| ^
|100| ^
|101| = 
|010| = 2 (am notat cu |a| reprezentarea binară a lui a)

La a doua ghicitoare avem: $n = 10$, $S = 14$. Numărul căutat este $5$. Intr-adevăr, S = 1 ^ 2 ^ 3 ^ 4 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10 are valoarea $14$.