Passing an exam is a tricky business.

There are two ways to pass an exam - 1. Study for the exam 2. Pray and have belief on your luck. Our dear friend has been pretty busy this whole semester in things other than study, if you know what I mean ;). So, he has not even seen the books. When the exams get close, he starts his study. But soon enough he understands that he will not be able to pass the exams by studying. So, he jumps on to the second option. LUCK. He finishes up his exam but the fear of flunking the exam does not allow him to sleep. He wants to know how much marks will he get, but teachers are not ready to tell him this. So, he decides to contact an astrologer. He goes to him with a single question paper at once.

The question paper has n questions. Each question is a string without any space. The astrologer tells him that if k is the number of e's in a question, he will get k mod (total marks for that question + 1) in that particular question. He is too nervous and wants you to help him calculate the marks he will get in each question.

INPUT:

t, the number of test cases.
For each test case following will be given:
s, the string that denotes the question. The string does not have space.
p, the total marks of the question.

OUTPUT:

For each test case output a single integer denoting the marks he will get as calculated using astrologer's method.

CONSTRAINTS:

1 <= t <= 100
1 <= length of s <= 1000
1 <= p <= 1000