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$

힌트