You are given a very long string which you need to generate from an initial number and some hashing function. Given below is the code to generate the string:

string S
make(int X, int N) { // X is the initial number, N is the length of the string
    for( i = 0: i < N : i++) {
        S.append(X+'a') // insert character that maps to integer X
                                    // 0 corresponds to 'a', and so on.
        X *= (ascii value of last character inserted in S)
        X += 31^(i) // 31 to the power i
        X %= 26
    }
}

After generating the string S, you need to find the value of the below function:

int get(S) {
    sort(S)
    vector V // Vector is just an array
    V.insert(1)
    for(int i=1;i<S.size();i++) {
        if ( S[i] == S[i-1]) {
            increment the value of last element in V
        }
        else {
            V.insert(1)
        }
    }
    int sum = 0
    bool add = true
    for (int i = 0; i < V.size() ; i++) {
        if(add) sum += V[i];
        else sum -= V[i];
        add ^= 1;
    }
    return sum
}

Can you help Rhezo calculate this weird thing above ^ ?

Input:

First line of input contains an integer T, denoting the number of test cases. Each test case contains 2 integers X and N.

Output:

For each test case, find the value returned by get function after passing in it the generated string S.

Constraints:

$1 \le T \le 10$

$0 \le X \lt 26$

$1 \le N \le 10^7$