Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.

Let's consider a rooted binary tree with the following properties:

The number of nodes and edges in the tree is infinite
The tree root is labeled by $1$
A node labeled by $v$ has two children: $2 \cdot v$ (the left child of $v$), and $2 \cdot v + 1$ (the right child of $v$).

Here is an image of the first several layers of such a tree:

Let's consider four operations that you are allowed to apply during the tree traversal:

move to the left child - move from $v$ to $2 \cdot v$
move to the right child - move from $v$ to $2 \cdot v + 1$
move to the parent as a left child - move from $v$ to $\frac{v}{2}$ if $v$ is an even integer
move to the parent as a right child - move from $v$ to $\frac{v - 1}{2}$ if $v$ is an odd integer

It can be proven, that for any pair of nodes $u$ and $v$, there is only one sequence of commands that moves from $u$ to $v$ and visits each node of the tree at most once. Let's call such a sequence of commands a path configuration for a pair of nodes $(u, v)$.

You are asked to process a series of the following queries: 

You are given three integers $n$, $u$ and $v$ ($1 ≤ u, v ≤ n$). Count the pairs of nodes $(w, t)$ ($1 ≤ w, t ≤ n$) such that the path configuration for $(w, t)$ is the same with the path configuration for $(u, v)$.

------  Input ------
The first line of input contains a single integer $Q$, denoting the number of queries to process.
Each of the next $Q$ lines contains three space-separated integers $n$, $u$ and $v$ denoting a query.

------  Output ------
For each query, print the answer on a separate line.

------  Constraints ------
$1 ≤ Q ≤ 2 \cdot 10^{4}$
$1 ≤ u, v ≤ n ≤ 10^{9}$

----- Sample Input 1 ------ 
3

11 9 11

10 2 2

8 1 8
----- Sample Output 1 ------ 
2

10

1
----- explanation 1 ------ 
In the first query from the example test case, you should count pairs $(5, 7)$ and $(9, 11)$.

In the second query from the example test case, you should count the following pairs: $(1, 1)$, $(2, 2)$, $(3, 3)$, $(4, 4)$, $(5, 5)$, $(6, 6)$, $(7, 7)$, $(8, 8)$, $(9, 9)$ and $(10, 10)$.

In the third query from the example test case, you should only count a pair $(1, 8)$.

Difficulty: HARD
Tags: Graph algorithms

Sorting

Complete search

Tree algorithms

Mathematics

Data structures

Tree queries
Skill types: Sorting

Data structures

Complete search

Starter code:

Solutions:
for t in range(int(input())):
	(n, p, q) = map(int, input().split())
	(v1, v2) = (n, n)
	while p != q:
		if p > q:
			if p & 1 == 1:
				v1 -= 1
			v1 //= 2
			p //= 2
		else:
			if q & 1 == 1:
				v2 -= 1
			v2 //= 2
			q //= 2
	print(min(v1, v2))


def main():
	n = int(input())
	for i in range(n):
		(n, u, v) = map(int, input().split())
		s = solve(n, u, v)
		print(s)

def solve(n, u, v):
	(ub, vb) = (bin(u)[2:], bin(v)[2:])
	i = 0
	while i < len(ub) and i < len(vb) and (ub[i] == vb[i]):
		i += 1
	return min(limit(n, ub[i:]), limit(n, vb[i:]))

def limit(n, sufix):
	if sufix == '':
		return n
	nb = bin(n)[2:]
	k = len(sufix)
	ns = nb[-k:]
	if sufix == ns or int(sufix, 2) < int(nb[-k:], 2):
		return int(nb[:-k], base=2)
	else:
		lb = nb[:-k]
		return int(lb, base=2) - 1
main()


Q = int(input())
while Q > 0:
	Q -= 1
	(N, u, v) = map(int, input().strip().split())
	if u > v:
		(u, v) = (v, u)
	(p, q) = (0, 1)
	while u != v:
		if u > v:
			u >>= 1
			continue
		if v & 1:
			p += q
		v >>= 1
		q <<= 1
	ans = (N - p) // q
	print(ans)


n = int(input())
for i in range(n):
	arr = input().split(' ')
	n = int(arr[0])
	u = int(arr[1])
	v = int(arr[2])
	if u > v:
		(u, v) = (v, u)
	path = []
	up = u
	vp = v
	while up != vp:
		if vp > up:
			if vp % 2 == 0:
				vp = vp // 2
				path.append(0)
			else:
				vp = vp // 2
				path.append(1)
		else:
			up = up // 2
	result = n
	for a in path:
		if a == 1:
			if result % 2 == 0:
				result -= 1
		elif result % 2 == 1:
			result -= 1
		result = result // 2
	print(result)