$p^{n}!$과 쿼리

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

문제 설명

예제1

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

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

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

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

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