提示: 欢迎访问OurACM平台。
Problem 1584 Sparse Big Integer

Accept: 85    Submit: 190
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

A big integer with most of its digits being zeros is called a sparse big integer. Given a sparse big integer M and an integer N, you are to calculate M mod N.

Input

The first line contains an integer representing the number of test cases. Each test case consists of two lines. In the first line of a test case, an integer K will be given first; then K pairs of integers follow, each indicates a non-zero digit with two integers D and P, which means the P-th digit of M from right to left is D. In the second line, the integer N will be given.

1 <= K <= 10; 1 <= D <= 9; 1 <= P <= 1000000000; 1 <= N <= 10000.

Output

For each test case, print the result of M mod N in a single line.

Sample Input

1
2 1 6 1 8
2046

Sample Output

944

Source

FOJ月赛-2008年4月

Submit  Back  Status  Discuss