번호 찾기

ABC 대학교에는 k개의 학과가 있다. 각 학과에는 학과 번호가 부여되어 있다. 각 학과에는 많은 학생이 있다. 대학교는 각 학생에게 학과 번호로 나누어떨어지는 번호를 학번으로 부여한다. 예를 들어 학과 번호가 5라면 학생은 5, 10, 15 등의 학번만 받을 수 있다. 이렇게 하는 이유는 학번만 보고 학생의 학과를 쉽게 알아내기 위해서이다. 따라서 어떤 수가 둘 이상의 학과 번호로 나누어떨어지면 그 수는 어떤 학생에게도 배정하지 않는다. 이렇게 해야 모호함이 생기지 않는다. 예를 들어 학과가 5와 7이라면 35, 70, 105 등은 두 수 모두로 나누어떨어지므로 사용하지 않는다.

모든 것이 잘 돌아가던 어느 날, 누군가 대학교 데이터베이스에 침입해 학생 테이블의 학번 열을 지워 버렸다! 데이터베이스 관리자는 다음 사실을 알고 있다.

• 10^15 미만의 모든 유효한 학번(유효한 학번이란 정확히 하나의 학과 번호로만 나누어떨어지는 수이다)이 데이터베이스에 있었다.
• 해커가 지우기 전에 모든 레코드는 학번 순으로 정렬되어 있었고, 해킹으로 인해 레코드의 순서는 바뀌지 않았다.

이제 데이터베이스에서 레코드의 위치(1부터 시작하는 인덱스)가 주어질 때, 그 레코드에 해당하는 학번을 빠르게 구할 수 있는가?

첫째 줄에는 테스트 케이스의 수 t가 주어진다. (1 ≤ t ≤ 50)

이어서 t개의 테스트 케이스가 주어지며, 각 테스트 케이스는 2개의 줄로 이루어진다.

• 각 테스트 케이스의 첫째 줄에는 공백으로 구분된 두 수 k와 n이 주어진다.
• 둘째 줄에는 각 학과의 학과 번호를 나타내는 k개의 정수가 공백으로 구분되어 주어진다.

각 테스트 케이스마다 데이터베이스의 n번째 레코드에 해당하는 학번을 출력한다. 각 테스트 케이스의 출력은 서로 다른 줄에 있어야 한다.

• 1 ≤ k ≤ 12
• 학과 번호는 2와 10^5 사이이다. (양 끝 포함)
• n은 32비트 부호 있는 정수 범위에 들어간다.
• 입력은 답이 항상 10^15 미만이 되도록 주어진다.
• 같은 번호를 가진 두 학과는 없다.
• 어떤 학과 번호도 다른 학과 번호로 나누어떨어지지 않는다.

첫 번째 테스트 케이스에서 학번의 나열은 2, 3, 4, 8 등이다. (6은 유효한 학번이 아님에 유의하라.) 따라서 이 나열의 네 번째 수는 8이다.