문제1124--순열 원소수 찾기 III

1124: 순열 원소수 찾기 III

시간제한 : 1.000 sec  메모리제한 : 128 MB

문제 설명

수학에서 집합은 주어진 성질을 만족시키는 대상들의 모임이다. 이러한 대상들을 집합의 원소라고 한다. 집합의 원소들은 서로 다르며, 같은 원소가 여러 개 있을 수는 없다.

어떤 집합에 원소가 X개 있다고 하자. 이 때, 원소의 수가 N개 늘어나 X+N개가 되면, 순열의 수가 K배 증가한다고 한다.

최초 집합의 원소 수 X는 얼마일까?

예를 들어, 집합 A={1, 2, 3} 라고 하자. 최초 원소의 수는 3개이므로 X=3 이다. 이 경우 생성할 수 있는 순열은 다음과 같이 총 6개(3!) 이다.

123

132

213

231

312

321

만약 원소의 수가 N=2개 늘어나 A={1, 2, 3, 4, 5} 가 되었다고 가정하자. 이 경우 순열은 120개(5!)로 20배 증가하게 된다.

N과 K가 주어졌을 때, X를 구하는 프로그램을 작성하자.

(입력 N, K 에 대해서 X는 항상 존재한다)

입력 설명

첫 줄에는 테스트 케이스 개수 T (1 <= T <= 50)가 주어진다.

그 다음 각 테스트 케이스 별로 한 줄에 N과 K가 주어진다. (2 <= N <= 4, 1 <= K <= 2^63 - 1)


출력 설명

각 테스트 케이스 별로 최초의 원소 수 X를 출력한다.


입력 예시 Copy

3
2 42
3 13800 
4 8960788732278099024

출력 예시 Copy

5
22
54710