SP186 LITELANG - The lightest language

Alphabet _A $ _{k} $_ consists of _k_ initial letters of English alphabet. A positive integer called a weight is assigned to each letter of the alphabet. A weight of a word built from the letters of the alphabet _A $ _{k} $_ is the sum of weights of all letters in this word. A language over an alphabet _A $ _{k} $_ is any finite set of words built from the letters of this alphabet. A weight of a language is the sum of weights of all its words. We say that the language is prefixless if for each pair of different words _w_, _v_ from this language _w_ is not a prefix of _v_. We want to find out what is the minimal possible weight of an _n_-element, prefixless language over an alphabet _A $ _{k} $_ .

The number of test cases _t_ is in the first line of input, then _t_ test cases follow separated by an empty line. In the first line of a test case there are two positive integers _n_ and _k_ separated by a single space, (2

For each test case you should output one line with the weight of the lightest prefixless _n_-element language over the alphabet _A $ _{k} $_ .