$p^{n}!$ 과 쿼리

시간 제한1초메모리 제한1024 MB

요약

소수 p와 정수 n이 주어질 때 (p^n)!에서 p의 지수를 구하는 쿼리를 처리한다.

문제

다음 쿼리를 수행하는 프로그램을 작성하자.

$p$ $n$ : 소수 $p$ 와 정수 $n$ 에 대해 $p^{n}!=p^k \times N$ 의 형태로 나타낼 때, $\gcd(p,N)=1$ 을 만족하는 정수 $k$ 의 값을 출력한다.

첫 번째 줄에 쿼리의 개수 $Q$ 가 주어진다.

두 번째 줄부터 $Q$ 개의 줄에 걸쳐 소수 $p$ 와 정수 $n$ 이 공백으로 구분되어 주어진다.

쿼리의 정답을 $10^9+7$ 로 나눈 나머지를 한 줄에 하나씩 순서대로 출력한다.

예제 1

입력

6
2 1
3 3
5 4
11 11
101 34890
999999937 1234

예상 출력