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₀a₁...a_b-1)_b

(that is m=a₀b^b-1+a₁b^b-2+...+a_b-2b+a_b-1, where 0≤a_i≤b-1 are integer)

ii) a_i is equal to the number of occurences of number i in the sequence (a₀a₁...a_b-1).

For example, (21200)₅ 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)₅ = (1425)₁₀ so 1425 is "self-descriptive" number.

Given n(1 ≤ n ≤10¹⁸)and m (1 ≤ m ≤ 10⁹), your task is to find the n-th smallest "self-descriptive" number.

Input

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

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)₄

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

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