Saurabh and Array

Saurabh formed an array by concatenating integers from **1 to n**, k times. Now he wants to know how many subarrays of any size are there such that sum of the subarray is **(n(n+1))/2**. ### Input The first line of the input is an integer t denoting the number of testcases. Then the ith line of the input contains two integers n and k (1 ≤ n ≤ 10^9, 1 ≤ k ≤ 10^9). ### Output Print t lines and in