1353_A. Most Unstable Array_36673
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.
t = int(input())
for i in range(t):
    n, m = map(int, input().split())
    if n >= 3:
        print(2 * m)
    if n == 2:
        print(m)
    if n == 1:
        print(0)

5
1 100
2 2
5 5
2 1000000000
1000000000 1000000000
 1
9041 222
 1
343800 343800
 1
9021 100
 1
9210 10000
 1
103 1
 1
9021 10000
 1
60 2
 2
12345 12345
1 1
 1
9021 5
 1
153 153
 1
153 6
 1
54 33
 1
153 10
 1
153 16
 1
1001 1
 1
53 100
 1
9022 222
 1
153 2
 1
103 5
 1
165 165
 1
154 1002
 1
70 70
 2
12345 12345
12345 12345
 1
165 1000
 1
9021 222
 1
53 5
 1
13616 222
 1
52916 343800
 1
10012 100
 1
6955 10000
 1
203 1
 1
9021 00000
 2
12345 6355
1 1
 1
9021 7
 1
214 153
 1
272 6
 1
153 9
 1
241 16
 1
1001 2
 1
9022 234
 1
104 5
 1
165 98
 1
162 1002
 1
70 86
 2
12345 12345
12345 10662
 1
165 1100
 5
1 100
2 0
5 5
2 1000000000
1000000000 1000000000
 1
13616 8
 1
52916 42716
 1
10012 110
 1
6955 11000
 1
9021 00010
 2
12345 2376
1 1
 1
2 33
 1
241 29
 1
165 172
 1
162 1590
 2
12345 12345
12345 16965
 1
13616 11
 1
52916 78612
 1
9021 10010
 1
152 151
 1
418 12
 1
256 14
 1
744 233
 1
17 150
 2
12345 12345
12345 10402
 1
101 3
 5
1 100
2 -1
5 5
2 1000000000
1000100000 1000000000
 1
52916 132417
 1
890 111
 2
3751 1500
1 1
 1
2654 15
 1
152 58
 1
256 23
 1
135 48
 1
106 101
 1
60 1
 1
1 33
 1
66 100
 1
231 2
 1
2340 222
 1
100 5
 1
242 1
 1
91 1
 1
2654 7
 1
152 153
 1
418 6
 1
256 9
 1
1011 2
 1
66 110
 1
744 234
 1
231 0
 1
201 5
 1
17 86
 1
123 1100
 1
2340 6
 1
101 5
 5
1 100
2 0
5 5
2 1000000000
1000100000 1000000000
 1
890 110
 1
2453 11000
 1
95 1
 1
91 2
 2
3751 2376
1 1
 1
2654 9
 1
135 29
 1
0001 2
 1
106 100
 1
201 8
 1
291 172
 1
320 1590
 1
123 0100
 1
2340 0
 1
19657 11
 1
2001 11000
 1
5 1
 1
4621 00010
 1
91 3
 1
719 12
 1
1163 233
 1
201 12
 1
181 172

0
2
10
1000000000
2000000000
 444
 687600
 200
 20000
 2
 20000
 4
 24690
0
 10
 306
 12
 66
 20
 32
 2
 200
 444
 4
 10
 330
 2004
 140
 24690
24690
 2000
 444
 10
 444
 687600
 200
 20000
 2
 0
 12710
0
 14
 306
 12
 18
 32
 4
 468
 10
 196
 2004
 172
 24690
21324
 2200
 0
0
10
1000000000
2000000000
 16
 85432
 220
 22000
 20
 4752
0
 33
 58
 344
 3180
 24690
33930
 22
 157224
 20020
 302
 24
 28
 466
 300
 24690
20804
 6
 0
-1
10
1000000000
2000000000
 264834
 222
 3000
0
 30
 116
 46
 96
 202
 2
 0
 200
 4
 444
 10
 2
 2
 14
 306
 12
 18
 4
 220
 468
 0
 10
 172
 2200
 12
 10
 0
0
10
1000000000
2000000000
 220
 22000
 2
 4
 4752
0
 18
 58
 0
 200
 16
 344
 3180
 200
 0
 22
 22000
 2
 20
 6
 24
 466
 24
 344
