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=a0bb-1+a1bb-2+...+ab-2b+ab-1, where 0≤ai≤b-1 are integer)

ii) a_i is equal to the number of occurrences 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 or 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