Chef is playing a game on the non-negative x-axis. It takes him $1$ second to reach from $i^{th}$ position to $(i-1)^{th}$ position or $(i+1)^{th}$ position. The chef never goes to the negative x-axis. Also, Chef doesn't stop at any moment of time.

The movement of chef can be described as follows.
At the start he is standing at $x=0$ at time $0$.
In the first round, he moves towards $x=1$ and comes back to the $x=0$ position. 
In the second round, he moves towards the $x=2$ and comes back again to $x=0$. 
Generalizing, in the $k^{th}$ round, he moves from $x=0$ to $x=k$ and then returns back to $x=0$ at the end of the round. This goes on as the game progresses.

For Example, the path of Chef for $3^{rd}$ round is given below.   
$0 - 1 - 2 - 3 - 2 - 1 - 0$        
  
The overall path followed by Chef would look somewhat like this:   
$0 - 1 - 0 - 1 - 2 - 1 - 0 - 1 - 2 - 3 - 2 - 1 - 0 - 1 - 2 - 3 - 4 - 3 - …$

You are given two non-negative integers $N$ and $K$. You have to tell the time at which Chef arrives at $x=N$ for the $K^{th}$ time. 

Note - Chef can not skip a position while visiting the positions.

------ Input: ------
The first line contains $T$ the number of test cases. Then the test cases follow.
Each test case contains a single line of two integers $N$ and $K$.

------ Output: ------
For each test case, print a single line containing one integer -- the time taken by the chef to arrive at $x=N$ for the $K^{th}$ time by modulo $1,000,000,007$.

------ Constraints  ------
$1 ≤ T ≤ 10^{5}$
$0 ≤ N ≤ 10^{9}$
$1 ≤ K ≤ 10^{9}$

----- Sample Input 1 ------ 
5
0 1
1 1
2 1
1 3
4 6
----- Sample Output 1 ------ 
0
1
4
5
46
----- explanation 1 ------ 
Test Case 1:  
Chef starts the journey from the $N = 0$ at time $t = 0$ and it's the first time $(K = 1)$, he is here. So, the answer is $0$.  

Test Case 2:  
Chef starts the journey from the $N = 0$ at time $t = 0$ then goes to $N = 1$ at $t = 1$ and it's the first time $(K = 1)$, he is here. So, the answer is $1$.

Test Case 4:   
The path followed by Chef to reach $1$ for the third time is given below.   
$0 - 1 - 0 - 1 - 2 - 1$   
He reaches $1$ for the third time at $t=5$.

Difficulty: MEDIUM_HARD
Tags: Mathematics

Starter code:

Solutions:
T = int(input())
for i in range(T):
	(n, k) = map(int, input().split())
	if n != 0:
		kk = k // 2
		nn = n + kk - 1
		nn = nn * (nn + 1)
		if k % 2 == 0:
			nn = (nn + n) % 1000000007
		else:
			nn = (nn + kk + n + kk) % 1000000007
		print(nn)
	else:
		k = k - 1
		k = k * (k + 1) % 1000000007
		print(k)


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	if n != 0:
		kk = k // 2
		nn = n + kk - 1
		nn = nn * (nn + 1)
		if k % 2 == 0:
			nn = (nn + n) % 1000000007
		else:
			nn = (nn + kk + n + kk) % 1000000007
		print(nn)
	else:
		k = k - 1
		k = k * (k + 1) % 1000000007
		print(k)


test = int(input())
MOD = int(1000000000.0 + 7)
for _ in range(test):
	(n, k) = [int(a) for a in input().split()]
	m = k // 2
	ans = (n + m) * (n + m) - m
	if k % 2:
		ans += 2 * m
	if n == 0:
		ans = k * (k - 1)
	print(ans % MOD)


T = int(input())
MOD = int(1000000000.0 + 7)
for t in range(T):
	(N, K) = [int(a) for a in input().split()]
	M = K // 2
	ans = (N + M) * (N + M) - M
	if K % 2:
		ans += 2 * M
	if N == 0:
		ans = K * (K - 1)
	print(ans % MOD)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	if n == 0 and k == 1:
		print(0)
	elif n == 0:
		print(k * (k - 1) % q)
	else:
		m = n + 1
		q = 10 ** 9 + 7
		if k % 2 == 0:
			m += k // 2 - 1
			print((m ** 2 + n - m) % q)
		else:
			m += (k + 1) // 2 - 1
			print((m ** 2 - n - m) % q)


t = int(input())
while t > 0:
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	if n == 0:
		tim = k * (k - 1)
		tim %= 1000000007
		print(tim)
	else:
		if k % 2 == 0:
			tim = n * n + n * k + k // 2 * (k // 2 - 1)
		else:
			tim = n * n + 2 * n * (k // 2) + k // 2 * (k // 2 + 1)
		tim %= 1000000007
		print(tim)
	t -= 1


MOD = 1000000007
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	x = n * (n - 1)
	if not n:
		print(k * (k - 1) % MOD)
	elif k & 1:
		print((2 * n + (n + (k - 1) // 2) * (n + (k - 1) // 2 + 1) - (n + 1) * n - n + x) % MOD)
	else:
		print((2 * n + (n + (k - 2) // 2) * (n + (k - 2) // 2 + 1) - (n + 1) * n + n + x) % MOD)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n == 0:
		print(k * (k - 1) % (10 ** 9 + 7))
	else:
		t = n * n
		t += k // 2 * (n * 2)
		t += (k + 1) // 2 * ((k + 1) // 2 - 1)
		print(t % (10 ** 9 + 7))


mod = 10 ** 9 + 7
from math import ceil, floor
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n == 0:
		print(k * (k - 1) % mod)
		continue
	if k == 0:
		print(0)
		continue
	else:
		print((n ** 2 + floor(k / 2) * 2 * n + ceil(k / 2) * ceil(k / 2 - 1)) % mod)


import math
t = int(input())
while t > 0:
	t = t - 1
	s = input().split(' ')
	n = int(s[0])
	k = int(s[1])
	k = k - 1
	ans = 0
	if n == 0:
		ans = k * (k + 1)
	elif k % 2 != 0:
		k = math.floor(k / 2)
		ans = (n + k) * (n + k + 1) + n
	else:
		k = math.floor(k / 2)
		ans = (n + k) * (n + k + 1) - n
	ans = ans % 1000000007
	print(ans)


t = int(input())
while t:
	mod = 1000000007
	(n, k) = list(map(int, input().split()))
	k %= mod
	if n == 0:
		print(k * (k - 1) % mod)
	else:
		ans = n * n
		ans %= mod
		ans += 2 * (k // 2) * n
		ans %= mod
		k = (k + 1) // 2
		ans += k * (k - 1)
		ans %= mod
		print(ans)
	t -= 1


mod = 1000000007
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = k // 2
	ans = 0
	if n == 0 and k == 1:
		ans = 0
	elif n == 0 and k > 1:
		ans = (k - 1) * k
	elif k == 1:
		ans = n * (n - 1) % mod
		ans = (ans + n) % mod
	elif k % 2 != 0:
		ans = (n + a) * (n + a + 1) % mod
		ans = (ans - n) % mod
	elif k % 2 == 0:
		ans = (n + a - 1) * (n + a) % mod
		ans = (ans + n) % mod
	print(ans % mod)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n == 0:
		t = k * (k - 1) % 1000000007
		print(t)
	elif k == 1:
		t = n ** 2 % 1000000007
		print(t)
	else:
		turn = k // 2
		p = turn + n
		if k % 2 == 0:
			print((p ** 2 - turn) % 1000000007)
		else:
			print((p ** 2 + turn) % 1000000007)


from math import ceil
mod = 10 ** 9 + 7

def sum_till_nth_term(n):
	return n * (2 + (n - 1)) % mod
for _ in range(int(input())):
	(N, K) = list(map(int, input().split()))
	ans = 0
	if K == 1:
		print(N ** 2 % mod)
	elif N == 0:
		print(sum_till_nth_term(K - 1))
	elif K > 1:
		ans += (N ** 2 + N) % mod
		K -= 1
		i = 1
		term_req = ceil(K / 2) - 1
		x = sum_till_nth_term(N)
		y = sum_till_nth_term(N + term_req)
		ans += (y - x) % mod
		K -= term_req * 2
		if K == 1:
			ans += N
			ans %= mod
		else:
			v = (N + (term_req + 1) * 2) % mod
			ans += v
			ans %= mod
		print(ans % mod)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	mod = 10 ** 9 + 7
	su = 0
	if n == 0:
		su = k * (k - 1)
	elif k % 2 == 0:
		k = k // 2 + n - 1
		su = k * (k + 1)
		su += n
	else:
		k = k // 2 + n
		su = k * (k + 1)
		su -= n
	print(su % mod)


def f():
	(n, k) = map(int, input().split(' '))
	if n == 0:
		return k * (k - 1) % (10 ** 9 + 7)
	if (k - 1) % 2 == 0:
		N = n + (k - 1) // 2
		t = -n + N * (N + 1)
	else:
		N = n + (k - 1) // 2
		t = n + N * (N + 1)
	return t % (10 ** 9 + 7)
for i in range(int(input())):
	print(f())


n = int(input())
for i in range(n):
	(x, y) = map(int, input().split(' '))
	c = 1000000007
	if x >= 0 and y > 0:
		if x > 0:
			if y % 2 != 0:
				k = (y - 1) // 2
				l = (x + k) ** 2
				print((l + k) % c)
			else:
				k = y // 2
				l = (x + k) ** 2
				print((l - k) % c)
		else:
			l = y ** 2
			print((l - y) % c)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	if a == 0:
		print(b * (b - 1) % 1000000007)
	elif b == 1:
		print(a * a % 1000000007)
	else:
		if b % 2 == 0:
			p = ((b - 2) // 2 + a) % 1000000007
			r = p * (p + 1) + a
		else:
			p = ((b - 1) // 2 + a) % 1000000007
			r = p * (p + 1) - a
		print(r % 1000000007)


M = 10 ** 9 + 7

def solve(n, k):
	count = n ** 2 % M
	if n == 0:
		count = (k - 1) * k % M
	elif k % 2 == 0:
		count = (count + n * k + (k - 2) * k // 4) % M
	else:
		count = (count + n * (k - 1) + (k - 1) * (k + 1) // 4) % M
	return count
for t in range(int(input().strip())):
	(n, k) = tuple(map(int, input().strip().split()))
	print(solve(n, k))


import math
mod = 10 ** 9 + 7
T = int(input())
for _ in range(T):
	(N, k) = map(int, input().strip().split())
	if N == 0:
		t = (k ** 2 - k) % mod
		print(t)
		continue
	l = math.ceil((k - 1) / 2) + N
	z = (k - 1) % 2
	t = l ** 2
	m = l - N
	if z == 0:
		t += m
	else:
		t -= m
	print(t % mod)


import collections

def solve(n, k):
	MOD = 10 ** 9 + 7
	if n == 0:
		return k * (k - 1) % MOD
	else:
		return (n ** 2 + k // 2 * 2 * n + (k + 1) // 2 * ((k + 1) // 2 - 1)) % MOD
t = int(input().strip())
for i in range(t):
	[n, k] = list(map(int, input().strip().split()))
	print(solve(n, k))


import math
MOD = int(1000000000.0 + 7)
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	m = k // 2
	x = (m + n) * (m + n) - m
	if k % 2 == 1:
		x += 2 * m
	if n == 0:
		x = k * (k - 1)
	print(x % MOD)


from math import pi
from collections import deque
from math import factorial
from math import log, ceil
from collections import defaultdict
from math import *
from sys import stdin, stdout
import itertools
import os
import sys
import threading
from collections import deque, Counter, OrderedDict, defaultdict
from heapq import *
from fractions import Fraction
mod = int(pow(10, 9) + 7)

def ii():
	return int(input())

def si():
	return str(input())

def mi():
	return map(int, input().split())

def li1():
	return list(mi())

def fii():
	return int(stdin.readline())

def fsi():
	return str(stdin.readline())

def fmi():
	return map(int, stdin.readline().split())

def fli():
	return list(fmi())
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}

def getKey(item):
	return item[0]

def sort2(l):
	return sorted(l, key=getKey)

def d2(n, m, num):
	return [[num for x in range(m)] for y in range(n)]

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def ntl(n):
	return [int(i) for i in str(n)]

def powerMod(x, y, p):
	res = 1
	x %= p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
graph = defaultdict(list)
visited = [0] * 1000000
col = [-1] * 1000000

def bfs(d, v):
	q = []
	q.append(v)
	visited[v] = 1
	while len(q) != 0:
		x = q[0]
		q.pop(0)
		for i in d[x]:
			if visited[i] != 1:
				visited[i] = 1
				q.append(i)
		print(x)

def make_graph(e):
	d = {}
	for i in range(e):
		(x, y) = mi()
		if x not in d:
			d[x] = [y]
		else:
			d[x].append(y)
		if y not in d:
			d[y] = [x]
		else:
			d[y].append(x)
	return d

def gr2(n):
	d = defaultdict(list)
	for i in range(n):
		(x, y) = mi()
		d[x].append(y)
	return d

def connected_components(graph):
	seen = set()

	def dfs(v):
		vs = set([v])
		component = []
		while vs:
			v = vs.pop()
			seen.add(v)
			vs |= set(graph[v]) - seen
			component.append(v)
		return component
	ans = []
	for v in graph:
		if v not in seen:
			d = dfs(v)
			ans.append(d)
	return ans

def primeFactors(n):
	s = set()
	while n % 2 == 0:
		s.add(2)
		n = n // 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			s.add(i)
			n = n // i
	if n > 2:
		s.add(n)
	return s

def find_all(a_str, sub):
	start = 0
	while True:
		start = a_str.find(sub, start)
		if start == -1:
			return
		yield start
		start += len(sub)

def SieveOfEratosthenes(n, isPrime):
	isPrime[0] = isPrime[1] = False
	for i in range(2, n):
		isPrime[i] = True
	p = 2
	while p * p <= n:
		if isPrime[p] == True:
			i = p * p
			while i <= n:
				isPrime[i] = False
				i += p
		p += 1
	return isPrime

def dijkstra(edges, f, t):
	g = defaultdict(list)
	for (l, r, c) in edges:
		g[l].append((c, r))
	(q, seen, mins) = ([(0, f, ())], set(), {f: 0})
	while q:
		(cost, v1, path) = heappop(q)
		if v1 not in seen:
			seen.add(v1)
			path = (v1, path)
			if v1 == t:
				return (cost, path)
			for (c, v2) in g.get(v1, ()):
				if v2 in seen:
					continue
				prev = mins.get(v2, None)
				next = cost + c
				if prev is None or next < prev:
					mins[v2] = next
					heappush(q, (next, v2, path))
	return float('inf')

def binsearch(a, l, r, x):
	while l <= r:
		mid = l + (r - 1) // 2
		if a[mid]:
			return mid
		elif a[mid] > x:
			l = mid - 1
		else:
			r = mid + 1
	return -1

def readTree(n):
	adj = [set() for _ in range(n)]
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u - 1].add(v - 1)
		adj[v - 1].add(u - 1)
	return adj

def treeOrderByDepth(n, adj, root=0):
	parent = [-2] + [-1] * (n - 1)
	ordered = []
	q = deque()
	q.append(root)
	depth = [0] * n
	while q:
		c = q.popleft()
		ordered.append(c)
		for a in adj[c]:
			if parent[a] == -1:
				parent[a] = c
				depth[a] = depth[c] + 1
				q.append(a)
	return (ordered, parent, depth)
for _ in range(ii()):
	(n, k) = mi()
	if n == 0:
		k -= 1
		ans = k * (k + 1) % mod
	elif k % 2 != 0:
		lr = k // 2
		ans = (n * n % mod + lr * (2 * n % mod) % mod + lr * (lr + 1) % mod) % mod
	else:
		lr = k // 2
		ans = (n * n % mod + lr * (2 * n) % mod % mod + lr * (lr - 1) % mod) % mod
	print(ans)


T = int(input())
for case in range(T):
	(N, K) = input().split()
	N = int(N)
	K = int(K)
	sec = 0
	first_loc = 0
	if N == 0:
		print((K ** 2 - K) % 1000000007)
	else:
		first_loc = N + K // 2
		sec = first_loc ** 2 - first_loc
		if K % 2 == 0:
			print((sec + N) % 1000000007)
		else:
			sec = (first_loc + 1) ** 2 - (first_loc + 1)
			print((sec - N) % 1000000007)


mod = int(1000000000.0 + 7)
for __ in range(int(input())):
	(n, k) = map(int, input().split())
	m = k // 2
	if k == 1:
		ans = n * n % mod
	elif n == 0:
		ans = k * (k - 1) % mod
	elif k % 2 == 0:
		ans = ((n + m) * (n + m) % mod - m) % mod
	elif k % 2 == 1:
		ans = ((n + m) * (n + m) % mod + m) % mod
	print(ans)


for t in range(int(input())):
	MOD = 1000000007
	(N, K) = map(int, input().split())
	M = K // 2
	ans = (N + M) * (N + M) - M
	if K % 2:
		ans += 2 * M
	if N == 0:
		ans = K * (K - 1)
	print(ans % MOD)


mod = 10 ** 9 + 7
for k in range(int(input())):
	(num, times) = map(int, input().split())
	if num == 0:
		x = times - 1
		ans = (x % mod * (x % mod) % mod + x % mod) % mod
	elif times % 2 == 0:
		x = num + (times - 1) // 2
		ans = (x % mod * (x + 1) % mod + x % mod + num % mod - x % mod) % mod
	else:
		x = num + (times - 1) // 2
		ans = (x % mod * (x + 1) % mod + x % mod - num % mod - x % mod) % mod
	print(ans)


tc = int(input())
for _ in range(tc):
	(n, k) = list(map(int, input().split()))
	if n == 0:
		summ = (k - 1) * k
	else:
		m = n + (k - 1) // 2
		if (k - 1) % 2 == 0:
			summ = m * (m + 1) - n
		else:
			summ = m * (m + 1) + n
	print(summ % 1000000007)


m = int(1000000000.0) + 7
for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	if n == 0:
		print((k - 1) * k % m)
	else:
		total = (n - 1) * n
		total = total % m
		x = k // 2
		a = n * x % m
		b = (x - 1) * x // 2 % m
		total += 2 * (a + b) % m
		total = total % m
		if k & 1 == 0:
			print((total + n) % m)
		else:
			print((total + (n + x) % m + x) % m)


module = 1000000007

def timeOfNthRound(n):
	if n % 2 != 0:
		r = n * (int(n / 2) + 1) % module
	if n % 2 == 0:
		r = (n - 1) * int(n / 2) % module + n
	return 2 * (r % module) % module
T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	if n == 0:
		result = timeOfNthRound(k - 1)
	else:
		result = timeOfNthRound(n + int(k / 2) - 1)
		if k == 1 or k % 2 == 0:
			result += n
		else:
			result += 2 * ((n + int(k / 2)) % module) - n
	result %= module
	print(result)


import math
for i in range(int(input())):
	l = list(map(int, input().split()))
	n = l[0]
	k = l[1]
	h = 10 ** 9 + 7
	if k == 1:
		print(n * n % h)
	elif n == 0:
		print(k * (k - 1) % h)
	elif k % 2 != 0:
		c = math.floor((k - 1) / 2)
		print(((n + c) * (n + c) + c) % h)
	else:
		c = math.floor(k / 2)
		print(((n + c) * (n + c) - c) % h)


ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda : int(input())
ip = lambda : [int(w) for w in input().split()]
mp = lambda : map(int, input().split())
M = 10 ** 9 + 7
for _ in range(int(input())):
	(n, k) = mp()
	if n == 0:
		ans = k * (k - 1)
		print(ans % M)
		continue
	ans = n * n % M
	ans += (2 * n - 1 + k // 2) * (k // 2) % M
	ans %= M
	if k % 2:
		ans += (k // 2 + k // 2) % M
	print(ans % M)


nn = int(input())
for _ in range(nn):
	(n, k) = map(int, input().split())
	r = n + (k - 1) // 2
	if n == 0:
		r = k - 1
		r = r * (r + 1) + 1
	elif (k - 1) % 2 != 0:
		r = r * (r + 1) + n + 1
	else:
		r = r * (r + 1) - (n - 1)
	print((r - 1) % 1000000007)


mod = 1000000007
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	if n == 0:
		ans = k * (k - 1)
		print(ans % mod)
	else:
		ans = n * n
		z = k - 1
		if z % 2 != 0:
			ans += (z // 2 + 1) * 2 * n
			p = z // 2
			ans += p * (1 + p)
		else:
			ans += z * n
			p = z // 2
			ans += p * (1 + p)
		print(ans % mod)


t = int(input())
mod = 1000000007
for i in range(t):
	(n, k) = map(int, input().split())
	if n == 0:
		res = k * (k - 1)
	elif k == 1:
		res = pow(n, 2)
	elif k > 1:
		c = (k - 1) // 2
		if k & 1 == 1:
			res = (n + c) * (n + c + 1) - n
		else:
			res = (n + c) * (n + c + 1) + n
	print(res % mod)


for t in range(int(input())):
	(n, k) = list(map(int, input().split()))
	if n == 0:
		ans = k * (k - 1)
	else:
		m = k - 1
		if m % 2 == 0:
			no = n + m // 2
			ans = no * no + (no - n)
		else:
			no = n + (m + 1) // 2
			ans = no * no - (no - n)
	print(ans % 1000000007)


mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a1 = n * n
	a2 = n * (n + 2)
	if n == 0:
		a2 = 2
		ans = k * (k - 1)
		print(ans % mod)
		continue
	d = (n + 1) * 2
	if k % 2 == 1:
		k = (k + 1) // 2
		k -= 1
		ans = a1 + k * (2 * d + (k - 1) * 2) // 2
	else:
		k //= 2
		k -= 1
		ans = a2 + k * (2 * d + (k - 1) * 2) // 2
	print(ans % mod)


mod = 1000000007
t = int(input())
while t > 0:
	b = input()
	b = b.split()
	n = int(b[0])
	k = int(b[1])
	if n == 0:
		print(k * (k - 1) % mod)
		t = t - 1
		continue
	dest = (n + k // 2) % mod
	ans = dest % mod * (dest + 1) % mod % mod
	if k % 2 == 0:
		ans = (ans % mod - (dest % mod - n % mod % mod) % mod - dest % mod) % mod
	else:
		ans = (ans % mod - n % mod) % mod
	print(ans)
	t -= 1


t = int(input())
for i in range(t):
	num1 = list(map(int, input().split()))
	n = num1[0]
	k = num1[1]
	b = 1000000007
	if n == 0:
		a = k * (k - 1)
		print(a % b)
	if n != 0:
		c = k % 2
		d = k // 2
		if c == 1:
			a = n ** 2 + d * n * 2 + d * (d + 1)
			print(a % b)
		if c == 0:
			a = n ** 2 + d * n * 2 + d * (d - 1)
			print(a % b)


mod = 1000000007
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	inc = k // 2
	nn = n + inc
	req = nn * nn
	if n == 0:
		ans = k * (k - 1)
	elif k % 2:
		ans = req + inc
	else:
		ans = req - inc
	print(ans % mod)


Mod = int(1000000000.0 + 7)

def solve(n, k):
	result = 0
	if n == 0:
		result = k * (k - 1)
		result = result % Mod
	elif k % 2 != 0:
		k1 = (n + int(k / 2)) % Mod
		k = k1
		k1 = k1 - 1
		result = k1 % Mod * (k1 + 1) % Mod % Mod
		result = (result % Mod + (k - 0) % Mod + (k - n) % Mod) % Mod
		result = result % Mod
	else:
		k1 = n + int((k - 1) / 2)
		result = k1 % Mod * (k1 + 1) % Mod % Mod
		result = (result % Mod + n % Mod) % Mod
	return result % Mod
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	print(solve(n, k))


T = int(input())
while T:
	(N, K) = map(int, input().split())
	M = 10 ** 9 + 7
	if N == 0:
		ans = K * (K - 1)
		print(ans % M)
	else:
		ans = N ** 2
		ans %= M
		ans += 2 * N * (K // 2)
		ans %= M
		ans += ((K + 1) // 2 - 1) * ((K + 1) // 2)
		print(ans % M)
	T -= 1


MOD = 1000000007
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	assert 0 <= n <= 10 ** 9 and 1 <= k <= 10 ** 9
	if n == 0:
		print(k * (k - 1) % MOD)
		continue
	if k == 0:
		print(0)
		continue
	start = n ** 2
	skip = n * 2
	ans = start + skip * (k // 2)
	k = -(-k // 2)
	ans += k * (k - 1)
	print(ans % MOD)


m = 1000000007
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n == 0:
		print(k * (k - 1) % 1000000007)
	else:
		x = k // 2
		if k % 2 == 0:
			t = (pow(n, 2) % m + 2 * n * x % m + (x - 1) * x % m) % m
			print(t)
		else:
			t = (pow(n, 2) % m + 2 * n * x % m + x * (1 + x) % m) % m
			print(t)


from sys import stdin, stdout
import math
from itertools import permutations, combinations
from collections import defaultdict
from bisect import bisect_left

def L():
	return list(map(int, stdin.readline().split()))

def In():
	return map(int, stdin.readline().split())

def I():
	return int(stdin.readline())
P = 1000000007
for t in range(I()):
	(n, k) = In()
	val = 0
	if n == 0:
		print(k % P * (k - 1) % P % P)
	else:
		val = n % P * (n % P) % P
		val += k // 2 % P * (2 * n) % P % P
		val += ((k + 1) // 2 - 1) % P * ((k + 1) // 2 % P) % P
		print(val % P)


m = 1000000007
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n == 0:
		print(k * (k - 1) % m)
		continue
	if k == 1:
		print(n ** 2 % m)
		continue
	if k == 2:
		print((n ** 2 + n * 2) % m)
		continue
	e = k // 2
	o = e - 1 if k % 2 == 0 else e
	print((n ** 2 + e * (2 * n) + o * (o + 1)) % m)


mod = pow(10, 9) + 7
t = int(input())
for t1 in range(0, t):
	(n, k) = map(int, input().split())
	z = 0
	if n == 0:
		z = k - 1
		z = z * (4 + (z - 1) * 2) // 2
		print(z % mod)
	else:
		n1 = n
		z = n1 * (4 + (n1 - 1) * 2) // 2
		if k == 1:
			z = z - (n - 1)
		else:
			k1 = k - 1
			if k1 % 2 == 0:
				k2 = k1 // 2
				n1 = n1 + k2
				z = n1 * (4 + (n1 - 1) * 2) // 2
				z = z - (n - 1)
			else:
				k2 = k1 // 2
				k2 = k2
				n1 = n1 + k2
				z = n1 * (4 + (n1 - 1) * 2) // 2
				z = z + n + 1
		print((z - 1) % mod)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	mod = 10 ** 9 + 7
	if n == 0:
		if k == 1:
			print(0)
		else:
			print(k * (k - 1) % mod)
	elif k % 2 == 0:
		res = n + k // 2 - 1
		print((res * (res + 1) + n) % mod)
	else:
		res = n + k // 2
		print((res * (res + 1) - n) % mod)


mod = 7 + 10 ** 9
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n == 0:
		print(k * (k - 1) % mod)
		continue
	l = k % 2
	k -= 1
	k //= 2
	k += n
	k = (2 * k + k * (k - 1)) % mod
	if l == 0:
		print((k + n) % mod)
	else:
		print((k - n) % mod)


t = int(input())
for i in range(t):
	(N, K) = map(int, input().split())
	if N == 0:
		res = K * (K - 1)
	else:
		res = N * N + K // 2 * (2 * N) + (K + 1) // 2 * ((K + 1) // 2 - 1)
	print(res % 1000000007)


mod = 1000000007
t = int(input())
for i in range(t):
	(n, k) = [int(i) for i in input().split()]
	if n == 0:
		print(k % mod * (k - 1) % mod % mod)
	else:
		k1 = k // 2
		if k % 2 == 0:
			print(((n + k1) % mod * (n + k1) % mod % mod - k1 % mod) % mod)
		else:
			print(((n + k1) % mod * (n + k1) % mod % mod + k1 % mod) % mod)


MOD = 10 ** 9 + 7

def f(n):
	return n * (n + 1)
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	ans = 0
	if n == 0:
		ans = f(k - 1)
	elif k == 1:
		ans = f(n) - n
	else:
		x = n + (k - 1) // 2
		if k % 2 == 0:
			ans = f(x) + n
		else:
			ans = f(x) - n
	print(ans % MOD)


t = int(input())
mod = 10 ** 9 + 7
for _ in range(t):
	(n, k) = map(int, input().split())
	if n == 0:
		print(k * (k - 1) % mod)
		continue
	no = k // 2 + 1
	up = no - 1 + n - 1
	up = up * (up + 1)
	od = no + n - 1
	if k % 2 == 0:
		print((up + n) % mod)
	else:
		print((up + od + od - n) % mod)


import sys
readLine = lambda : sys.stdin.readline()
readInt = lambda : int(sys.stdin.readline())
readInts = lambda : [int(x) for x in sys.stdin.readline().split(' ')]
MOD = 1000000007
for _ in range(readInt()):
	(n, k) = readInts()
	print((k - 1) * k % MOD if n == 0 else (n ** 2 + 2 * n * (k // 2) + (k - 1) // 2 * ((k - 1) // 2 + 1)) % MOD)


m = 10 ** 9 + 7
for i in range(int(input())):
	(n, k) = map(int, input().split())
	if n == 0:
		c = k - 1
		su = (c + 1) * c
		print(su % m)
		continue
	if k % 2 == 0:
		c = n + k // 2 - 1
		su = c * (c + 1) + n
		print(su % m)
	else:
		c = n + k // 2 - 1
		su = (c + 2) * (c + 1) - n
		print(su % m)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	t1 = n * (n + 1)
	if n == 0 and k == 1:
		t1 = 0
	elif n == 0 and k > 1:
		t1 = k * (k - 1)
	elif k == 1:
		t1 = t1 - n
	else:
		p = int((k - 1) / 2)
		if (k - 1) % 2 == 1:
			t1 = t1 + p * 2 * n + p * (p + 1) + n
		else:
			t1 = t1 + p * 2 * n + p * (p + 1) - n
	print(t1 % (10 ** 9 + 7))


mod = 10 ** 9 + 7
for ii in range(int(input())):
	(n, k) = map(int, input().split())
	if n == 0:
		print(k * (k - 1) % mod)
	else:
		print((n * n + k // 2 * 2 * n + (k + 1) // 2 * ((k + 1) // 2 - 1)) % mod)


md = 10 ** 9 + 7
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a == 0:
		b = b - 1
		sm = b * (4 + (b - 1) * 2) // 2 % md
		print(sm)
		continue
	val = b // 2
	if b % 2 == 0:
		val -= 1
	sm = (a + val) * (4 + (a + val - 1) * 2) // 2 % md
	if b % 2 == 0:
		sm += a
		sm %= md
	else:
		sm -= a
		sm %= md
	print(sm)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	mod = 1000000007
	if n == 0:
		print(k * (k - 1) % 1000000007)
	else:
		sq = n * n % mod
		k -= 1
		z = 2 * n % mod
		m = k // 2
		if k % 2 == 0:
			sq = (sq + m * (m + 1) % mod + z * m % mod) % mod
		else:
			sq = (sq + m * (m + 1) % mod + z * (m + 1) % mod) % mod
		print(sq)


t = int(input())
mod = int(1000000000.0 + 7)
for i in range(t):
	(N, K) = [int(a) for a in input().split()]
	M = K // 2
	ans = (N + M) * (N + M) - M
	if K % 2:
		ans += 2 * M
	if N == 0:
		ans = K * (K - 1)
	print(ans % mod)


mod = int(1000000000.0 + 7)
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	k = m // 2
	ans = ((n + k) * (n + k) % mod - k) % mod
	if m % 2:
		ans += 2 * k
	if n == 0:
		ans = m * (m - 1)
	print(ans % mod)


t = int(input())
for _ in range(t):
	[n, k] = [int(x) for x in input().split()]
	if n == 0:
		print((k - 1) * k % 1000000007)
		continue
	if k % 2 == 0:
		x = int(k / 2) - 1
		print(((n + x) * (n + x + 1) + n) % 1000000007)
	else:
		x = int((k - 3) / 2)
		print(((n + x) * (n + x + 1) + n + 2 * x + 2) % 1000000007)


def main():
	from bisect import bisect_left as bl, bisect_right as br, insort
	import sys
	import heapq
	from collections import defaultdict as dd, deque

	def data():
		return sys.stdin.readline().strip()

	def mdata():
		return list(map(int, data().split()))
	out = sys.stdout.write
	INF = int(1000000000.0)
	mod = int(1000000000.0) + 7
	for t in range(int(data())):
		(n, k) = mdata()
		if n == 0:
			if k == 1:
				print(0)
			else:
				ans = k * (k - 1)
				print(ans % mod)
			continue
		ans = n * n + k // 2 * 2 * n + (k - 1 - k // 2) * (k - k // 2)
		print(ans % mod)
main()


t = int(input())
mod = 10 ** 9 + 7
while t > 0:
	(n, k) = map(int, input().split())
	if n == 0:
		time = k * (k - 1)
	elif k == 1:
		time = n * (n - 1)
		time = (time + n) % mod
	else:
		k -= 1
		if k % 2 == 0:
			z = k // 2
			l = n + z - 1
			time = l * (l + 1)
			time = (time + n + z + z) % mod
		else:
			z = k + 1
			z = z // 2
			l = n + z - 1
			time = l * (l + 1)
			time = (time + n) % mod
	print(time % mod)
	t -= 1


_MOD = 1000000007
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	if n == 0:
		print(k * (k - 1) % _MOD)
		continue
	no = k / 2
	if no == int(no):
		print(((n + int(no)) * (n + int(no)) - int(no)) % _MOD)
	else:
		print(((n + int(no)) * (n + int(no)) + int(no)) % _MOD)


t = int(input())
mod = 1000000007
for _ in range(t):
	(n, k) = map(int, input().split(' '))
	if n == 0:
		print(k * (k - 1) % mod)
	else:
		a = n + k // 2
		ans = pow(a, 2, mod)
		if k % 2 == 0:
			ans = (ans - k // 2 + mod) % mod
		else:
			ans = (ans + k // 2) % mod
		print(ans)


t = int(input())
mod = 10 ** 9 + 7

def add(a, b, m):
	if a + b >= m:
		return (a + b) % m
	return a + b

def mul(a, b, m):
	if a * b < m:
		return a * b
	return a * b % m
for _ in range(t):
	(n, k) = [int(x) for x in input().strip().split()]
	res = pow(n, 2, mod) % mod
	if n == 0:
		print((k - 1) * k % mod)
	else:
		k -= 1
		if k % 2 == 0:
			a1 = k // 2
		else:
			a1 = k // 2 + 1
		a2 = k - a1
		k1 = mul(a1, 2 * n, mod) % mod
		k2 = add(a2, 1, mod) % mod
		k2 = mul(k2, a2, mod) % mod
		res = add(k1, res, mod) % mod
		res = add(res, k2, mod) % mod
		print(res % mod)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n == 0 and k == 1:
		print(0)
	else:
		m = 1000000007
		if n == 0:
			total = (k - 1) * (2 * 2 + (k - 1 - 1) * 2) // 2
		else:
			l1 = n + 1
			k1 = k // 2
			total = (l1 + k1 - 2) * (2 * 2 + (l1 + k1 - 2 - 1) * 2) // 2 % m
			if k == 1:
				total += n % m
			elif k % 2 == 0:
				total += n % m
			else:
				total += (l1 + k1 - 1 + (l1 + k1 - 1 - n)) % m
		print(total % m)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	if n == 0:
		print(((k - 1) ** 2 + k - 1) % (10 ** 9 + 7))
	else:
		if k % 2 == 1:
			a = (k + 1) // 2 + 1
			flag = 1
		else:
			a = k // 2 + 1
			flag = 2
		cntbr = (a - 1 + n - 1) ** 2
		b = a + n - 1
		z = b * 2 - 1
		c = z // 2
		if flag == 1:
			cntaf = c - n
		else:
			cntaf = z - (c - n) - 1
		print((cntaf + cntbr) % (10 ** 9 + 7))


T = int(input())
for _ in range(T):
	nk = input().split()
	n = int(nk[0])
	k = int(nk[1])
	if n != 0:
		if k % 2 == 1:
			print(int((n ** 2 + n * (k - 1) + (k ** 2 - 1) // 4) % 1000000007))
		else:
			print(int((n ** 2 + k * n + k // 2 * (k // 2 - 1)) % 1000000007))
	else:
		print(int(k * (k - 1) % 1000000007))


mod = 1000000007
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n == 0:
		if k == 1:
			print(0)
			continue
		else:
			k1 = (k - 1) * (4 + (k - 1 - 1) * 2) // (1 + 1)
			print(k1 % mod)
			continue
	k1 = n * (4 + (n - 1) * 2) // (1 + 1)
	if k == 1:
		print((k1 - n) % mod)
		continue
	k -= 1
	if k % (1 + 1) != 0:
		k //= 1 + 1
		t = (n + k) * (4 + (n + k - 1) * (1 + 1)) // (1 + 1)
		print((t + n) % mod)
	else:
		k //= 1 + 1
		t = (n + k) * (4 + (n + k - 1) * (1 + 1)) // (1 + 1)
		print((t - n) % mod)


import sys
from random import choice, randint
inp = sys.stdin.readline
out = sys.stdout.write
flsh = sys.stdout.flush
sys.setrecursionlimit(10 ** 9)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def MI():
	return map(int, inp().strip().split())

def LI():
	return list(map(int, inp().strip().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines().strip()]

def LI_():
	return [int(x) - 1 for x in inp().strip().split()]

def LF():
	return [float(x) for x in inp().strip().split()]

def LS():
	return inp().strip().split()

def I():
	return int(inp().strip())

def F():
	return float(inp().strip())

def S():
	return inp().strip()

def pf(s):
	return out(s + '\n')

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

def main():
	from math import ceil
	t = I()
	l = []
	for _ in range(t):
		(n, k) = MI()
		if n == 0:
			k -= 1
			ans = k * (k + 1) % mod
			l.append(ans)
		elif k % 2 != 0:
			lr = k // 2
			l.append((n * n % mod + lr * (2 * n % mod) % mod + lr * (lr + 1) % mod) % mod)
		else:
			lr = k // 2
			l.append((n * n % mod + lr * (2 * n) % mod % mod + lr * (lr - 1) % mod) % mod)
	for i in range(t):
		pf(str(l[i]))
main()


try:
	t = int(input())
	for _ in range(t):
		(a, b) = map(int, input().split())
		if a == 0:
			print((b - 1) * b % 1000000007)
		else:
			c = b % 2
			if c == 0:
				x = (b - 2) // 2
				ans = (a + x) * (a + x + 1) + a
				print(ans % 1000000007)
			else:
				x = b // 2
				ans = (a + x - 1) * (a + x)
				ans = ans + a + 2 * x
				print(ans % 1000000007)
except:
	pass


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	m = 10 ** 9 + 7
	if n == 0:
		if k == 1:
			print(0)
		else:
			print(k * (k - 1) % m)
	elif k == 1:
		print((n * (n - 1) + n) % m)
	elif k % 2:
		x = n + (k - 1) // 2
		print((x * (x + 1) - n) % m)
	else:
		x = n + k // 2
		print((x * (x - 1) + n) % m)