Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Reverse Number

By ashikurrahman · Limits 5s, 512 MB

You are given an integer NN and a digit DD. You have to count the number of pairs AA and BB (1A,BN){(1 \le A, B \le N)} such that

  1. AA and BB do not contain any leading zeros

  2. Last digit of AA is equal to the first digit of BB

  3. First digit of AA is equal to last digit of BB and

  4. Except for the the first and last digits of both integer AA and BB, there must be at least one digit present in both AA and BB which is equal to the given digit DD.

Print the answer modulo 10000000071000000007(109+7)(10^{9} + 7).

Input

First line contains an integer TT (T100000){(T \le 100000)} denoting test cases. Then TT line follows two space separated integers NN and DD.

1<=N<=10181 <= N <= 10^{18}

0<=D<=90 <= D <= 9

Output

Print a single line the the number of pair satisfy the condition for each test cases.

Sample

InputOutput
5
111 1
222 2
245 3
555 3
100 5
1
4
4
25
0


    Discussion

    Statistics


    50% Solution Ratio

    kzvd4729Earliest, 6M ago

    YouKnowWhoFastest, 1.2s

    kzvd4729Lightest, 1.0 MB

    Deshi_TouristShortest, 1532B

    Submit

    Login to submit

    Editorial

    A digit DP problem. Fix the first and last digit using loop and try to calculate how many numbers sa...

    Toph uses cookies. By continuing you agree to our Cookie Policy.