33680번 - $p^{n}!$과 쿼리

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

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

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

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

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

• $1 \leq Q \leq 100\,000$
• $2 \leq p \leq 10^9$, $p$는 소수
• $1 \leq n \leq 10^9$