You step into your first data structures class, where you are learning about binary search. You heard the professor yapping about why binary search works in $O(\log{n})$. But you want to see if you can find a better bound.

Given a sorted array $a$ of size $n$ and an integer $k$, define $f(a, k, l, r)$ as the result of the following code:

function f(a, k, l, r):
   if a does not contain k:
      return 0
   mid = floor((l+r) / 2)
   if a[mid]==k:
      return 1
   else if a[mid]<k:
      return 1+f(a, k, mid+1, r)
   else:
      return 1+f(a, k, l, mid-1)

You are given two integers $n$ and $m$. Define an array $a$ good if:

• $|a|=n$ (there are $n$ elements in $a$).
• $1 \leq a_1 \leq a_2 \leq \ldots \leq a_n \leq m$ (the array is nondecreasing, bounded by $1$ below and bounded by $m$ above).

You are interested in finding the sum of $f(a,1,1,n)+f(a,2,1,n)+\ldots+f(a,m,1,n)$ over all good arrays $a$. Since this answer may be huge, output the answer modulo $676\,767\,677$. Note that $676\,767\,677$ is a prime number.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($3 \leq n,m \leq 10^6$).

It is guaranteed that the sum of $n$ does not exceed $10^6$ over all test cases, and the sum of $m$ does not exceed $10^6$ over all test cases.

Output

For each test case, output the requested sum modulo $676\,767\,677$ on a new line.

Note

In the first test case, one good array $a$ is $[2,2,3]$. Here, $f(a,1,1,n)=0$ (as $1$ is not present in $a$), $f(a,2,1,n)=1$, $f(a,3,1,n)=2$. Therefore, the contribution of this good array is $0+1+2=3$.