SELFDESN - Self Descriptive Number

A positive integer m is called "self-descriptive" in base b, where b≥2 and b is an integer, if:

i) The representation of m in base b is of the form (a0a1...ab-1)b

(that is m=a0bb-1+a1bb-2+...+ab-2b+ab-1, where 0≤ai≤b-1 are integer)

ii) ai is equal to the number of occurrences of number i in the sequence (a0a1...ab-1).

For example, (21200)5 is "self-descriptive" in base 5, because it has five digits and contains two 0s, one 1s, two 2s, and no (3s or 4s).

(21200)5 = (1425)10 so 1425 is "self-descriptive" number.

Given n (1 ≤ n ≤1018) and m (1 ≤ m ≤ 109), your task is to find the n-th smallest "self-descriptive" number.

Input

The first line there is an integer T (1 ≤ T ≤ 105).

For each test case there are two integers n and m written in one line, separated by a space.

Output

For each test case, output the n-th smallest "self-descriptive" number, (output the number in base 10) modulo m.

Example

Input:
2
1 1000
2 1000

Output:
100
136

Explanation

100 is "self descriptive" number in base 4: (1210)4

136 is "self descriptive" number in base 4: (2020)4

Time limit ~230x My program speed: Click here to see my submission history and time record for this problem

See also: Another problem added by Tjandra Satria Gunawan


Added by:Tjandra Satria Gunawan
Date:2013-04-28
Time limit:25s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IMC 2009 + My Idea to modify that problem

hide comments
2017-03-02 15:21:59
edited. thanks

Last edit: 2017-03-06 04:30:46
2013-05-10 22:54:29 Michael Kharitonov
Can you prove that there are no nontrivial self-descriptive numbers?
Ans(Tjandra): of course ;-)

Last edit: 2013-05-11 05:21:02
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.