Lotus has $n$ kinds of characters,each kind of characters has a value and a amount.She wants to construct a string using some of these characters.Define the value of a string is:its first character's value*1+its second character's value *2+...She wants to calculate the maximum value of string she can construct.
Since it's valid to construct an empty string,the answer is always $\geq 0$ĄŁ
Input
First line is $T(0 \leq T \leq 1000)$ denoting the number of test cases.
For each test case,first line is an integer $n(1 \leq n \leq 26)$,followed by $n$ lines each containing 2 integers $val_i,cnt_i(|val_i|,cnt_i\leq 100)$,denoting the value and the amount of the ith character.
Output
For each test case.output one line containing a single integer,denoting the answer.
