You are given a number \(N\) represented as a binary representation of \(X = 16\) bits. You are also given a number \(m\) and a character \(c\ (L\ or\ R) \).

Determine a number \(M\) that is generated after cyclically shifting the binary representation of \(N\) by \(m\) positions either left if \(c = L\) or right is \(c = R\).

Input format 

1. The first line contains an integer \(T\) representing the number of queries.
2. The next \(T\) lines contain \(N\ m\ c\) as mentioned in the problem statement.

Output format

Print \(T\) integers in a separate line representing the answer to each query.

Constraints
\(1 \le T \le 1e4\\ 1  \le N \le 65535\\ 1 \le m \le 15\)