Shift Letters

Interview

Time limit1sMemory limit128 MB

Summary

For each test case, rotate the letters of a word right by n positions and print the result in a fixed sentence format.

Level: Easy2 of 10
Topics: String, Implementation, Simulation
Solved: No attempts yet

Problem

Bilbo wants to send a message to the dwarves, who are currently being held prisoner by the Great Goblin. He has a way to get it to them, but there is a chance the orcs may intercept the message. So he decides to encrypt it using a very simple scheme (enough to fool the orcs, who are not known for their intelligence).

Specifically, he shifts the letters of every word in the message to the right by a small amount, wrapping the overflow around to the front. For example, shifting "oakenshield" by 3 gives "eldoakenshi", whereas shifting "gandalf" by 2 gives "lfganda". He shifts every word by a different number of letters, always less than the number of letters in that word.

Write a program to help Bilbo encode his message.

Input

The first line contains the number of test cases $T$ ( $T < 100$ ). Each of the following lines contains one test case: a word $w$ (a string) followed by an integer $n$ . You may assume that $0 < n < |w|$ .

Output

For each test case, output a single line containing the word formed by shifting every letter of $w$ to the right by $n$ and wrapping around to the front. Use exactly the following format:

Shifting w by n positions gives us: result

where w is the original word, n is the shift amount, and result is the shifted word.

Examples4

Example 1

Input

3
hobbit 2
unexpected 3
journey 4

Expected output

Shifting hobbit by 2 positions gives us: ithobb
Shifting unexpected by 3 positions gives us: tedunexpec
Shifting journey by 4 positions gives us: rneyjou

Example 2

Input

2
oakenshield 3
gandalf 2

Expected output

Shifting oakenshield by 3 positions gives us: eldoakenshi
Shifting gandalf by 2 positions gives us: lfganda

Example 3

Input

1
ab 1

Expected output

Shifting ab by 1 positions gives us: ba

Example 4

Input

4
cat 1
dog 2
elephant 5
mouse 3

Expected output

Shifting cat by 1 positions gives us: tca
Shifting dog by 2 positions gives us: ogd
Shifting elephant by 5 positions gives us: phantele
Shifting mouse by 3 positions gives us: usemo