You are given two integers n and m. You have to construct the array a of length n consisting of non-negative integers (i.e. integers greater than or equal to zero) such that the sum of elements of this array is exactly m and the value ∑_{i=1}^{n-1} |a_i - a_{i+1}| is the maximum possible. Recall that |x| is the absolute value of x.

In other words, you have to maximize the sum of absolute differences between adjacent (consecutive) elements. For example, if the array a=[1, 3, 2, 5, 5, 0] then the value above for this array is |1-3| + |3-2| + |2-5| + |5-5| + |5-0| = 2 + 1 + 3 + 0 + 5 = 11. Note that this example doesn't show the optimal answer but it shows how the required value for some array is calculated.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases. Then t test cases follow.

The only line of the test case contains two integers n and m (1 ≤ n, m ≤ 10^9) — the length of the array and its sum correspondingly.

Output

For each test case, print the answer — the maximum possible value of ∑_{i=1}^{n-1} |a_i - a_{i+1}| for the array a consisting of n non-negative integers with the sum m.

Example

Input


5
1 100
2 2
5 5
2 1000000000
1000000000 1000000000


Output


0
2
10
1000000000
2000000000

Note

In the first test case of the example, the only possible array is [100] and the answer is obviously 0.

In the second test case of the example, one of the possible arrays is [2, 0] and the answer is |2-0| = 2.

In the third test case of the example, one of the possible arrays is [0, 2, 0, 3, 0] and the answer is |0-2| + |2-0| + |0-3| + |3-0| = 10.
################ code used from the given problem ################
##################################################################
# class TreeNode:
#     def __init__(self, val):
#         self.val = val
#         self.right = None
#         self.left = None
 
 
# def create_bst(input_list, start_index, end_index):
#     if start_index > end_index:
#         return None
#     elif start_index == end_index:
#         node = TreeNode(input_list[start_index])
#         return node
#     mid = int((start_index + end_index) / 2)
#     root = TreeNode(input_list[mid])
#     root.left = create_bst(input_list, start_index, mid - 1)
#     root.right = create_bst(input_list, mid + 1, end_index)
#     return root
 
# # Use this function and pass input list for obtaining bst
# def get_bst(input_list):
#     return create_bst(input_list, 0, len(input_list) - 1)
 
# ##################################################################

# def main():
#     '''
#     use stdin to input the list and pass it to the get_bst() function above
# 	for obtaining the root of the BST.
 
# 	Code for reference.
 
# 	root = get_bst(input_list);
#     '''
#     # Start writing code from here
#     def fun(root,a,b):
#     	if root:
#     		if a<=root.val and b>=root.val:
# 	    		return root
# 	    	if a>=root.val and b>=root.val:
# 	    		fun(root.right,a,b)
# 	    	elif a<=root.val and b<=root.val:
# 	    		fun(root.left,a,b)
#     def do(root,b,dic,ans):
#     	ans[dic[root.val]] +=1
#     	if root.val==b:
#     		return 
#     	else:
#     		if b<root.val:
#     			return do(root.left,b,dic,ans)
#     		else:
#     			return do(root.right,b,dic,ans)
#     n,m = map(int,input().split())
#     arr = list(map(int,input().split()))
#     root = get_bst(arr)
#     dic = {}
#     for i in range(n):
#     	dic[arr[i]] = i
#     ans = [0]*n
#     for i in range(m):
#     	a,b = map(int,input().split())
#     	a,b = min(a,b),max(a,b)
#     	x = fun(root,a,b)
#     	ans[dic[x.val]]-=1
#     	do(x,a,dic,ans)
#     	do(x,b,dic,ans)
#     print(ans)

# if __name__ == '__main__':
#     main()
# s = 'piku'
# ans = []
# n = len(s)
# def fun(s,i,n):
# 	if i==len(n):
# 		



for _ in range(int(input())):
	n,m = map(int,input().split())
	if n == 1:
		print(0)
	elif n==2:
		print(m)
	else:
		print(2*m)
