The whole world is crazy about subset sum. We define subset sum as sum of all subparts. A subpart is a number which is obtained by erasing certain digits and arranging the remaining numbers in the same order. You have to calculate the subset sum of the given number. Since the number can be very large return the subset sum modulo m.

For example if the number is 1357, then the various subparts are 1, 3, 5, 7, 13, 15, 17, 35, 37, 57, 137, 135, 157, 357, 1357.

Input

First line contains T (1 ≤ T ≤ 50) denoting the number of test cases.

Next T lines containing two numbers n (0 < n < 10¹⁰⁰⁰) and m(1 < m < 10⁹).

Output

Print the subset sum modulo m.

Example

Input:
6
111 9
111 200
456 9
456 1000
1357 1000
1357 5000

Output:
3
147
6
618
333
2333

Time Limit ≈ 2*(My Python 3 Program Top Speed)

See also: Another problem added by Tjandra Satria Gunawan