Ayoub thinks that he is a very smart person, so he created a function f(s), where s is a binary string (a string which contains only symbols "0" and "1"). The function f(s) is equal to the number of substrings in the string s that contains at least one symbol, that is equal to "1".

More formally, f(s) is equal to the number of pairs of integers (l, r), such that 1 ≤ l ≤ r ≤ |s| (where |s| is equal to the length of string s), such that at least one of the symbols s_l, s_{l+1}, …, s_r is equal to "1". 

For example, if s = "01010" then f(s) = 12, because there are 12 such pairs (l, r): (1, 2), (1, 3), (1, 4), (1, 5), (2, 2), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 4), (4, 5).

Ayoub also thinks that he is smarter than Mahmoud so he gave him two integers n and m and asked him this problem. For all binary strings s of length n which contains exactly m symbols equal to "1", find the maximum value of f(s).

Mahmoud couldn't solve the problem so he asked you for help. Can you help him? 

Input

The input consists of multiple test cases. The first line contains a single integer t (1 ≤ t ≤ 10^5) — the number of test cases. The description of the test cases follows.

The only line for each test case contains two integers n, m (1 ≤ n ≤ 10^{9}, 0 ≤ m ≤ n) — the length of the string and the number of symbols equal to "1" in it.

Output

For every test case print one integer number — the maximum value of f(s) over all strings s of length n, which has exactly m symbols, equal to "1".

Example

Input


5
3 1
3 2
3 3
4 0
5 2


Output


4
5
6
0
12

Note

In the first test case, there exists only 3 strings of length 3, which has exactly 1 symbol, equal to "1". These strings are: s_1 = "100", s_2 = "010", s_3 = "001". The values of f for them are: f(s_1) = 3, f(s_2) = 4, f(s_3) = 3, so the maximum value is 4 and the answer is 4.

In the second test case, the string s with the maximum value is "101".

In the third test case, the string s with the maximum value is "111".

In the fourth test case, the only string s of length 4, which has exactly 0 symbols, equal to "1" is "0000" and the value of f for that string is 0, so the answer is 0.

In the fifth test case, the string s with the maximum value is "01010" and it is described as an example in the problem statement.
import java.io.*;
import java.util.*;

public class Main {
	static InputStream inputStream = System.in;
	static OutputStream outputStream = System.out;
	static InputReader in = new InputReader(inputStream);
	static PrintWriter out = new PrintWriter(outputStream);

	public static void main(String[] args) throws IOException {
		int t = 1;
		t = in.nextInt();
		while (t-- > 0) {
			solve();
		}
		out.close();

	}

	static int mod = 1000000007;

	public static class Pair {
		long val;
		int idx;

		public Pair(long v, int i) {
			this.val = v;
			this.idx = i;
		}

	}

	private static void solve() {
		long n = in.nextLong();
		long m = in.nextLong();

		long z = n - m;
		long pp = m + 1; // possible positions

		long len = z / pp;

		long ex = z % pp; // extras

//		we have ex - with 1 extra zero
//		and each having equally divided zeroes of len 

//		all possible substrings - substrings with consecutive zeroes

		long tot = n * (n + 1) / 2;
		long zss = pp * (len * (len + 1) / 2) + ex * (len + 1);
		long res = tot - zss;

		out.println(res);
	}

//	int n = in.nextInt();
//	int[] a = new int[n];
//	for (int i = 0; i < n; i++) {
//		a[i] = in.nextInt();
//	}
	private static boolean pow2(int i) {
		return (i & (i - 1)) == 0;
	}

	private static void sort(int[] arr) {
		int n = arr.length;
		ArrayList<Integer> res = new ArrayList<>();
		for (int a : arr) {
			res.add(a);
		}
		Collections.sort(res);
		for (int i = 0; i < n; i++) {
			arr[i] = res.get(i);
		}
	}

	private static ArrayList<Integer> sieveOfEratosthenes(int n) {
		boolean[] arr = new boolean[n + 1];

		arr[0] = arr[1] = true;
		for (int i = 2; i * i <= n; i++) {
			if (!arr[i]) {
				for (int j = i * i; j <= n; j += i) {
					arr[j] = true;
				}
			}
		}
		ArrayList<Integer> primes = new ArrayList<>();
		for (int i = 2; i <= n; i++) {
			if (!arr[i]) {
				primes.add(i);
			}
		}
		return primes;
	}

	private static ArrayList<Integer> segmentedSieve(int s, int e) {
		int len = (int) (Math.sqrt(e) + 1);
		ArrayList<Integer> primes = sieveOfEratosthenes(len);
		boolean[] arr2 = new boolean[e - s + 1];
		if (s == 1) {
			arr2[0] = true;
		}
		ArrayList<Integer> res = new ArrayList<>();
		for (int p : primes) {

			int st = (int) (p * (Math.ceil((double) s / p)));
			if (st < s) {
				st += p;
			}
			if (st == p) {
				st += p;
			}
			for (int i = st; i <= e; i += p) {
				arr2[i - s] = true;
			}
		}
		for (int i = 0; i < arr2.length; i++) {
			if (!arr2[i]) {
				res.add(i + s);
			}
		}
		return res;
	}

	private static long pow(int n, int k) {
		long res = 1;
		long num = (long) n;
		while (k > 0) {
			if ((k & 1) == 1) {
				res = (res * num) % mod;
			}
			k /= 2;
			num = num * num % mod;
		}
		return res;
	}

	private static void set(int[] bits, int a) {
		for (int i = 31; i >= 0 && a > 0; i--) {
			int bit = a & 1;
			if (bit == 1) {
				bits[i]++;
			}
			a = a >> 1;
		}
	}

	private static void unset(int[] bits, int a) {
		for (int i = 31; i >= 0 && a > 0; i--) {
			int bit = a & 1;
			if (bit == 1) {
				bits[i]--;
			}
			a = a >> 1;
		}
	}

	private static int countDigits(int n) {
		int c = 0;
		while (n != 0) {
			c++;
			n /= 10;
		}
		return c;
	}

	private static int[] getRange(int a) {
		int min = 1;
		int t = a;
		while (--t > 0) {
			min = min * 10;
		}
		int max = 9;
		t = a;
		while (--t > 0) {
			max = max * 10 + 9;
		}
		return new int[] { min, max };
	}

	private static boolean palindrome(String str) {
		int s = 0;
		int e = str.length() - 1;
		while (s < e) {
			if (str.charAt(s) != str.charAt(e)) {
				return false;
			}
			s++;
			e--;
		}
		return true;
	}

	private static void reverse(int[] arr, int s, int e) {
		while (s < e) {
			int temp = arr[s];
			arr[s++] = arr[e];
			arr[e--] = temp;
		}
	}

	private static int getMax(int[] arr, int s, int e) {
		int maxi = s;
		for (int i = s + 1; i <= e; i++) {
			if (arr[i] > arr[maxi]) {
				maxi = i;
			}
		}
		return maxi;
	}

	private static int getMin(int[] arr, int s, int e) {
		int mini = s;
		for (int i = s + 1; i <= e; i++) {
			if (arr[i] < arr[mini]) {
				mini = i;
			}
		}
		return mini;
	}

	private static long lcm(long n1, long n2) {
		return (n1 * n2) / gcd(n1, n2);
	}

	private static long gcd(long num1, long num2) {
		if (num2 == 0) {
			return num1;
		}
		return gcd(num2, num1 % num2);
	}

	private static int lcm(int n1, int n2) {
		return (n1 * n2) / gcd(n1, n2);
	}

	private static int gcd(int num1, int num2) {
		if (num2 == 0) {
			return num1;
		}
		return gcd(num2, num1 % num2);
	}

	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public String nextLine() throws IOException {
			return reader.readLine().trim();
		}
	}
}