说明

x < 10 f(x) = x. 
x >= 10 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + ...... + a9 * f(x-10);
s(x)=f(1)+f(2)+f(3)+...+f(x)
给你一个数n和m，求s(n)%m

输入格式

输入一个T（T<=1000），表示有T组测试样例，每组数据输入n(n<1000000000)和m(m<1000000000)
以及a0,a1,a2,...,a9(ai为0或者1)

输出格式

s(n)%m

2
10 9999
1 1 1 1 1 1 1 1 1 1
20 500
1 0 1 0 1 0 1 0 1 0

90
175