Time Limit: 1000 MS    Memory Limit: 65536 K 


Description

Given a very big integer X. Can you tell me X%m ?

Input

The first line of the input data will be a integer to represent the number of test cases. For each test case there is only one line contains two integers X and m. ( 0 <= X <= 10^1000 , 1 <= m <= 10^5 ) There is a blank line before each test case.

Output

For each test case output the answer on a single line.

Sample Input

3 0 100 123456789123456789 54321 123456789123456789123456789123456789 100000

Sample Output

0 20520 56789

Source

7th SCUPC

by windy7926778