
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
//import java.util.TreeSet;

public class Main
 {
	public static void main(String Args[])throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int t = Integer.parseInt(st.nextToken());
		while(t-->0)
		{
			st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int k = Integer.parseInt(st.nextToken());
			if(k==0)
			{
				System.out.println(0);
				continue;
			}
			int div = (k+1);
			String zeros = "";
			for(int i = 1;i<=(n)/(k)-1;i++)
			{
				zeros = zeros+"0";
			}
			String s = "";
			for(int i = 1;i<div;i++)
			{
				s = s+zeros+"1";
			}
//			s = s+zeros;
			if(s.length()!=n)
			{
				int diff = n-s.length();boolean f = true;
				
				for(int i = 1;i<=diff;i++)
				{
					if(f)
						s += "0";
					else
						s = "0"+s;
					f=!f;
				}
					
			}
//			System.out.println(s);
			getans(s);
//			s= br.readLine();
//			getans(s);
			
		}
	}

	private static void getans(String s) {
		int n = s.length();
		// TODO Auto-generated method stub
		int lastpos[] = new int[n+1];
		Arrays.fill(lastpos, -1);
		for(int i = 1;i<=n;i++)
		{
			char c = s.charAt(i-1);
			if(c-'0'==1)
			lastpos[i] = i;
			if(i!=0)
			lastpos[i] = Math.max(lastpos[i-1],lastpos[i]);
		}
//		System.out.println(Arrays.toString(lastpos));
		int dp[] = new int[n+1];
		for(int i = 1;i<=n;i++)
		{
			char c = s.charAt(i-1);
			
			dp[i] = dp[i-1];
			if(c-'0'==1)
			{
				dp[i] += i;
			}
			else if(lastpos[i]!=-1)
				dp[i] += lastpos[i];
		}
//		System.out.println(Arrays.toString(dp));
		System.out.println(dp[n]);
	}

 }