18936번 - 신기한 공놀이

문제

주머니 안에 A개의 공이 있고, 그중에 정확히 B개의 빨간색 공이 있다. (A ≥ B ≥ 1, A ≠ 1)

공놀이를 하려 주머니에서 공을 꺼내던 현이는 우연히도 무작위로 두 개의 공을 뽑았을 때 적어도 하나는 빨간색이 아닐 확률이 자연수 N에 대해 정확히 1/N²이 됨을 알고 신기해했다.

현이는 주어진 N에 대해 이 조건을 만족하는 자연수의 쌍 (A, B)이 무한히 많음을 곧 깨달았고, 그중 A가 M번째로 작은 쌍은 무엇인지 궁금해졌다.

현이는 공놀이를 자주 해서 궁금증 또한 자주 생길 것이다. 당신은 궁금증을 해소해 주기 위해 현이가 공놀이를 Q번 하는 동안 모두 답을 해주어야 한다!

입력

첫 번째 줄에 공놀이를 하는 횟수 Q가 주어진다.

두 번째 줄부터 Q+1번째 줄까지 각 줄마다 자연수 N, M이 공백으로 구분되어 주어진다.

출력

Q개의 줄에 각 줄마다 조건을 만족하는 자연수의 쌍 (A, B)중 A가 M번째로 작은 쌍을 공백으로 구분하여 출력한다. 수가 매우 커질 수 있으니 10⁹+7로 나눈 나머지를 출력한다.

제한

• 1 ≤ Q ≤ 10⁵
• 1 ≤ N ≤ 10⁹
• 1 ≤ M ≤ 10¹⁸

힌트