Everybody in MIT knows Krishna Sundar is a cool, young and energetic DP programmer, whereas Vaidyanathan Pk is a young and romantic programmer. According to Krishna, energy is needed to code. But Vaidhy thinks that, to be a coder, you need to be romantic. Whenever the math professor asks any questions, it is Vaidhy who answers it first. Frustrated by his act, Krishna Sundar decided to answer the questions before Vaidhy does. One fine day, the math professor gave the question, which is to be asked in the class, to the class representative, Swagath. Swagath is close friend of Krishna Sundar and he has a grudge with Pk for being so romantic. So he gave the questions to Krishna before the class started, with the hope that he would answer first.

The question is slightly tougher this time. Krishna Sundar has turned towards you for help. The question is as follows:

You are given a string of digits, let s1, s2, s3,..,sn be all the substrings of the original string, which do not contain leading zeros which are all palindromes.

Now, consider the following function F(n, k) = n, if n == k F(n, k) = k * (1 + F(n, k+1))

Find (F(s1,1)+F(s2,1)+F(s3,1)+...+F(sn,1))%m, considering s1, s2, s3… sn as integers. Help him beat the romantic programmer.

Input Format The first line contains ite, the number of test cases. For each test case, the first line contains the string s. The next line contains the mod value, m.

Output Format Print ite lines, each containing the answer.

Input Constraints 1<=ite<=100 |s| <= 1000 1<=m<100