A numerical triad of limit N is a set of 3 numbers A, B and C where 0 ≤ A,B,C ≤ N. A numerical triad of limit N is considered a beautiful triad in base K, if and only if all the pairs that can be formed between their values A, B and C differ by no more than K units. For example (4, 4, 6) is a beautiful triad in base 3 because the difference between A and B is 0, the difference between A and C is 2 and the difference between B and C is 2, all differences being less than 3. However, this is not a beautiful triad in base 1, because two of their differences are greater than 1. Knowing N and K, can you tell how many different beautiful triads of limit N in base K can be formed? Note that (4, 4, 6), (4, 6, 4) and (6, 4, 4) are three different triads. Input The first line of the input contains an integer T, the number of test cases. Each case contains two integers N and K as described previously (0 ≤ N ≤ 2∗109, 0 ≤ K ≤ 1000, K ≤ N). Output Print one line per test case, the number of beautiful triads of limit N in base K that can be formed. It is guaranteed that this number fits in a 64 bits signed integer. Sample Input 5 00 10 11 21 2000000000 0 Sample Output 1 2 8 15 2000000001