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.
	/*
	TO LEARN
	1-segment trees
	2-euler tour
	3-fenwick tree and interval tree
	*/
	/*
	TO SOLVE 
	uva 1103
	program codeforces edu 102 D
	*/
	/*
	bit manipulation shit
	1-Computer Systems: A Programmer's Perspective
	2-hacker's delight
	3-(02-03-bits-ints)
	4-machine-basics
	5-Bits Manipulation tutorialspoint
	*/
	/*
	TO WATCH
	1-what is bitmasking by kartik arora youtube

	*/
	            import java.util.*;
			    import java.math.*;
			    import java.io.*; 
			    import java.util.stream.Collectors;

			       public class A{
			     
			  static InputStream inputStream = System.in;
	            static FastScanner scan=new FastScanner();
			     public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
	

		public static void main(String[] args)  throws Exception 
	      {
		
			//	scan=new FastScanner("help.in");
			//out = new PrintWriter("lifeguards.out");
			 
			 /*
			 currently doing 
			 1-digit dp
			 2-ds like fenwick and interval tree and sparse table 
			 */
			 /*
			 READING 
			 1-Everything About Dynamic Programming codeforces
			 2-DYNAMIC PROGRAMMING: FROM NOVICE TO ADVANCED topcoder
			 3-Introduction to DP with Bitmasking codefoces
			 4-Bit Manipulation hackerearth
			 5-read more about mobious and inculsion-exclusion 
			 */
			


			    int tt=1;
			 tt=scan.nextInt();

		 outer:while(tt-->0)
			    {
			    	long n=scan.nextLong(),m=scan.nextLong();
			    	if(m>=n/2)
			    	{
			    		long num=n*(n+1)/2;
			    		out.println(num-(n-m));
			    	}
			    	else 
			    	{
			    		long todivide=m+1;
			    		long num=(n-m)/todivide;
			    		long mod=(n-m)%todivide;
			    		long first=(((num+1)*(num+2))/2)*mod;
			    		long second=(m+1)-mod;
			    		second=second*(num*(num+1)/2);
			    		out.println((n*(n+1)/2)-(first+second));
			    	}
			    		
	

	}

			  	    out.close();
	 		  
			   
			}
			static class special{
				long x1,y1,x2,y2;
				//int id;
				special(long x1,long y1,long x2,long y2)
				{
					this.x1=x1;
					this.y1=y1;
					this.x2=x2;
					this.y2=y2;
					//this.id=id;
				}
				@Override
				    public int hashCode() {
			                int hash = 7;
    hash = 31 * hash + (int) x1;
    hash = 31 * hash + (int)x2;
    hash = 31 * hash + (int)y1;
    hash = 31 * hash + (int)y2;
    return hash;
			            }
			              @Override
			            public boolean equals(Object o){
			                if (o == this) return true;
			                if (o.getClass() != getClass()) return false;
			                special t = (special)o;
			                return t.x1 == x1 && t.y1 == y1&&t.x2==x2&&t.y2==y2;
			            }
			}

			   
			     static long binexp(long a,long n)
			    {
			        if(n==0)
			            return 1;
			        long res=binexp(a,n/2);
			        if(n%2==1)
			            return res*res*a;
			        else 
			            return res*res;
			    }
			     
			    static long powMod(long base, long exp, long mod) {
			           if (base == 0 || base == 1) return base;
			           if (exp == 0) return 1;
			           if (exp == 1) return (base % mod+mod)%mod;
			           long R = (powMod(base, exp/2, mod) % mod+mod)%mod;
			           R *= R;
			           R %= mod;
			           if ((exp & 1) == 1) {
			               return (base * R % mod+mod)%mod;
			           }
			           else return (R %mod+mod)%mod;
			       }
			    static double dis(double x1,double y1,double x2,double y2)
			    {
			        return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
			    }
			    static long mod(long x,long y)
			        {
			            if(x<0)
			                x=x+(-x/y+1)*y;
			            return x%y;
			        }
			     public static  long pow(long b, long e) {
			                long r = 1;
			                while (e > 0) {
			                    if (e % 2 == 1) r = r * b ;
			                    b = b * b;
			                    e >>= 1;
			                }
			                return r;
			            }
			    private static void sort(long[] arr) {
			            List<Long> list = new ArrayList<>();
			            for (long object : arr) list.add(object);
			            Collections.sort(list);
			        //Collections.reverse(list);
			            for (int i = 0; i < list.size(); ++i) arr[i] = list.get(i);
			        }
			    private static void sort2(long[] arr) {
			            List<Long> list = new ArrayList<>();
			            for (Long object : arr) list.add(object);
			            Collections.sort(list);
			        Collections.reverse(list);
			            for (int i = 0; i < list.size(); ++i) arr[i] = list.get(i);
			        }
			     static class FastScanner
	{
	    private int BS = 1 << 16;
	    private char NC = (char) 0;
	    private byte[] buf = new byte[BS];
	    private int bId = 0, size = 0;
	    private char c = NC;
	    private double cnt = 1;
	    private BufferedInputStream in;
	 
	    public FastScanner() {
	        in = new BufferedInputStream(System.in, BS);
	    }
	 
	    public FastScanner(String s) {
	        try {
	            in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
	        } catch (Exception e) {
	            in = new BufferedInputStream(System.in, BS);
	        }
	    }
	 
	    private char getChar() {
	        while (bId == size) {
	            try {
	                size = in.read(buf);
	            } catch (Exception e) {
	                return NC;
	            }
	            if (size == -1) return NC;
	            bId = 0;
	        }
	        return (char) buf[bId++];
	    }
	 
	    public int nextInt() {
	        return (int) nextLong();
	    }
	 
	    public int[] nextInts(int N) {
	        int[] res = new int[N];
	        for (int i = 0; i < N; i++) {
	            res[i] = (int) nextLong();
	        }
	        return res;
	    }
	 
	    public long[] nextLongs(int N) {
	        long[] res = new long[N];
	        for (int i = 0; i < N; i++) {
	            res[i] = nextLong();
	        }
	        return res;
	    }
	 
	    public long nextLong() {
	        cnt = 1;
	        boolean neg = false;
	        if (c == NC) c = getChar();
	        for (; (c < '0' || c > '9'); c = getChar()) {
	            if (c == '-') neg = true;
	        }
	        long res = 0;
	        for (; c >= '0' && c <= '9'; c = getChar()) {
	            res = (res << 3) + (res << 1) + c - '0';
	            cnt *= 10;
	        }
	        return neg ? -res : res;
	    }
	 
	    public double nextDouble() {
	        double cur = nextLong();
	        return c != '.' ? cur : cur + nextLong() / cnt;
	    }
	 
	    public double[] nextDoubles(int N) {
	        double[] res = new double[N];
	        for (int i = 0; i < N; i++) {
	            res[i] = nextDouble();
	        }
	        return res;
	    }
	 
	    public String next() {
	        StringBuilder res = new StringBuilder();
	        while (c <= 32) c = getChar();
	        while (c > 32) {
	            res.append(c);
	            c = getChar();
	        }
	        return res.toString();
	    }
	 
	    public String nextLine() {
	        StringBuilder res = new StringBuilder();
	        while (c <= 32) c = getChar();
	        while (c != '\n') {
	            res.append(c);
	            c = getChar();
	        }
	        return res.toString();
	    }
	 
	    public boolean hasNext() {
	        if (c > 32) return true;
	        while (true) {
	            c = getChar();
	            if (c == NC) return false;
	            else if (c > 32) return true;
	        }
	    }
	}

			     static class Pair implements Comparable<Pair>{
			            public long x, y,z;
			            public Pair(long x1, long y1,long z1) {
			                x=x1;
			                y=y1;
			                z=z1;
			            }
			             public Pair(long x1, long y1) {
			                x=x1;
			                y=y1;
			    
			            }
			            
			            @Override
			            public int hashCode() {
			                return (int)(x + 31 * y);
			            }
			            public String toString() {
			                return x + " " + y+" "+z;
			            }
			            @Override
			            public boolean equals(Object o){
			                if (o == this) return true;
			                if (o.getClass() != getClass()) return false;
			                Pair t = (Pair)o;
			                return t.x == x && t.y == y&&t.z==z;
			            }
			    public int compareTo(Pair o)
			    {
			    
			    	return (int)(x-o.x);
			     
			        }
			     
			    }
			    
			    }

			     
