提示: 欢迎访问OurACM平台
Problem 2108 Mod problem

Accept: 106    Submit: 438
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Given one non-negative integer A and one positive integer B, it’s very easy for us to calculate A Mod B. Here A Mod B means the remainder of the answer after A is divided by B. For example, 7 Mod 5 = 2, 12 Mod 3 = 0, 0 Mod 3 = 0.

In this problem, we use the following rules to express A.

(1) One non-empty string that only contains {0,1,2,3,4,5,6,7,8,9} is valid.

For example, 123, 000213, 99213. (Leading zeros is OK in this problem)

(2) If w is valid, then [w]x if valid. Here x is one integer that 0<x<10.

For example, [012]2=012012, [35]3[7]1=3535357.

(3) If w and v are valid, then wv is valid.

For example, w=[231]2 and v=1, then wv=[231]21 is valid (which is 2312311).

Now you are given A and B. Here A is express as the rules above and B is simply one integer, you are expected to output the A Mod B.

Input

The first line of the input contains an integer T(T≤10), indicating the number of test cases.

Then T cases, for any case, only two lines.

The first line is one non-empty and valid string that expresses A, the length of the string is no more than 1,000.

The second line is one integer B(0<B<2,000,000,000).

You may assume that the length of number A in decimal notation will less than 2^63.

Output

For each test case, output A Mod B in a single line.

Sample Input

3 [0]9[[1]2]3 10007 [[213231414343214231]5]1 10007 [0012]1 1

Sample Output

1034 3943 0

Source

“高教社杯”第三届福建省大学生程序设计竞赛

Submit  Back  Status  Discuss