SP14751 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 (a $ _{0} $ a $ _{1} $ ...a $ _{b-1} $ ) $ _{b} $ > (that is _m_=a $ _{0} $ b $ ^{b-1} $ +a $ _{1} $ b $ ^{b-2} $ +...+a $ _{b-2} $ b+a $ _{b-1} $ , where 0 ii) a $ _{i} $ is equal to the number of occurences of number i in the sequence (a $ _{0} $ a $ _{1} $ ...a $ _{b-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 and 4s). (21200) $ _{5} $ = (1425) $ _{10} $ so 1425 is "self-descriptive" number. Given **n**(1 n m (1 m n-th smallest "self-descriptive" number.

The first line there is an integer **T** (1 T For each test case there are two integers **n** and **m** written in one line, separated by a space.

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