During his analytic algebra class, Huy was very interested in lucky numbers, lucky numbers are those whose last digits are the lucky digit k for him. So when he sees some integer n, Huy immediately tries to find the number d (d ≥ 2), such that n represented in the base d system has the largest possible number of last digits, is k. That is, for another base numbering system, even if n has a certain number of digits ending in k, that number cannot be larger than the number when representing n in the system. base d.

Please help Huy write a program to find the base d system and the maximum number of lucky digits that n can represent.

Input:

Each test contains multiple test cases.

• The first line contains a single integer t (1 ≤ t ≤ ~10^3~) — the number of test cases. Each test case consists of two lines.
• Next t lines, each line contains 2 integers n and k, each number separated by at least one space (1 ≤ n ≤ ~10^11~; 0 ≤ k ≤ 9).

Output:

For each test case, prints two integers: the first number is d (the base to be searched), the second number is x (the number of digits k at the end when representing n in the base d number system). If multiple bases d have the same number of x, give the first base found.

Example

Input

2
49 1
7 5

Output

3 2
0 0

Note:

• The first testcase, the number 49 in base 10 is represented in base 3 as 1211 consists of 2 digits 1 at the end.
• The second testcase, the number 7 in any base number never has a 5 as the last digit.