Một cặp số nguyên dương \((x, y)\) được gọi là bí ẩn nếu với \(a, b\) lần lượt là số ước dương lẻ và số ước dương chẵn của \(x \cdot y\) ta có tổng \(GCD(a, b) + LCM(a, b)\) là một số lẻ. Trong đó \(GCD(a, b)\) là ước chung lớn nhất của \(a\) và \(b\), \(LCM(a,b)\) là bội chung nhỏ nhất của \(a\) và \(b\).

Gọi \(S\) là tập hợp gồm \(k\) số nguyên phân biệt \(\{S_1, S_2, \ldots, S_k\}\). Xét đồ thị gồm \(k\) đỉnh đánh số từ \(1\) tới \(k\). Với mọi cặp \(1 \leq u,v \leq k\), nếu \(S_u\) và \(S_v\) là một cặp bí ẩn thì ta nối một cạnh có hướng nối từ \(u\) tới \(v\). Gọi \(d(u,v)\) là độ dài đường đi ngắn nhất từ \(u\) với \(v\), nếu \(u\) không có đường đi tới \(v\) thì \(d(u,v)=10^{18}\). Độ bí ẩn của tập hợp \(S\) sẽ là \(\max\limits_{1 \leq u,v \leq k}\{d(u,v)\}\). Cho hai số nguyên dương \(n\) và \(k\), với mọi tập hợp \(S\) gồm \(k\) số nguyên phân biệt thỏa \(1 \leq S_i \leq n\), tìm độ bí ẩn nhỏ nhất và số lượng tập hợp có độ bí ẩn nhỏ nhất.

Lưu ý: Hai tập hợp là khác nhau khi tồn tại ít nhất một phần tử xuất hiện trong tập này mà không xuất hiện ở tập kia.

Input

• Dòng đầu chứa số nguyên \(q\) (\(1 \leq q \leq 10\)) là số test.
• Trong \(q\) dòng tiêp theo, mỗi dòng chứa hai số nguyên \(n\) và \(k\) (\(1 \leq n, k \leq 10^{12}\)).

Output

• Với mỗi test, in ra hai số nguyên là độ bí ẩn nhỏ nhất và số lượng tập hợp có độ bí ẩn nhỏ nhất. Vì kết quả có thể rất lớn nên hãy in các kết quả chia lấy dư cho \(10^9+7\). Nếu không tồn tại tập hợp nào thì in \(-1\) và \(0\).
• Lưu ý, việc so sánh các độ bí ẩn là so sánh theo giá trị thật, không phải so sánh theo giá trị sau khi chia lấy dư. Ví dụ \(10^9 + 7 > 1\).

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n \leq 10\)
• Subtask \(2\) (\(10\%\) số điểm): \(n \leq 10^5\) và \(k = 2\)
• Subtask \(3\) (\(20\%\) số điểm): \(n \leq 10^7\) và \(k = 3\)
• Subtask \(4\) (\(15\%\) số điểm): \(n,k \leq 10^5\)
• Subtask \(5\) (\(15\%\) số điểm): \(n,k \leq 10^7\)
• Subtask \(6\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

1
4 2

1 1