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 \leq u, v \leq n$). Count the pairs of nodes $(w, t)$ ($1 \leq w, t \leq 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 \leq Q \leq 2 \cdot 10^4$
- $1 \leq u, v \leq n \leq 10^{9}$

-----Example Input-----
3
11 9 11
10 2 2
8 1 8

-----Example Output-----
2
10
1

-----Explanation-----
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)$.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 't = int(input())\nwhile(t>0):\n t-=1;\n n,l,r = list(map(int,input().split()));\n a = bin(l)[2:];\n b = bin(r)[2:];\n # find matching\n z = 0;\n l = min(len(a),len(b));\n for i in range(l):\n  if a[i]==b[i]:\n   z+=1;\n  else:\n   break;\n\n #find base string\n a = a[z:]\n b = b[z:]\n if(len(a)==0 and len(b)==0):\n  print(n);\n else :\n  m = max(len(a),len(b))\n  #print m;\n  zz = bin(n)[2:]\n  x= len(zz)\n  y = zz[:x-m]\n  \n  f1 = y+a;\n  f2 = y+b;\n  ans = int(y,2)\n  if(int(f1,2)>n or int(f2,2)>n):\n   ans-=1;\n  \n  print(ans) \n  \n\n  \n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13539