Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FR_04_09 - Silnia

 

Silnia
Niech k oznacza iloczyn wszystkich liczb pierwszych od 2 do z . Zadanie polega na znalezieniu
maksymalnego p, takiego ze równanie: 
n! mod k^p = 0;
jest prawdziwe.
np. dla n=10 i z=5  :
10!=3628800
iloczyn wszystkich liczb pierwszych od 2 do 5 = 2*3*5=30;
10!= 30^2 * 4032
czyli 10! mod 30^2 = 0;
p=2;

Niech k oznacza iloczyn wszystkich liczb pierwszych od 2 do z . Zadanie polega na znalezieniu maksymalnego p, takiego ze równanie: 

n! mod kp ≡ 0

jest prawdziwe.

Wyjaśnienie

np. dla n=10 i z=5

10!=3628800

iloczyn wszystkich liczb pierwszych od 2 do 5 wynosi

2⋅3⋅5 = 30

10! = 302  4032

czyli

10! mod 302 ≡ 0

gdzie p=2.

Wejście

W pierwszym wierszu jedna liczba t określająca liczbę zestawów danych (t < 10001).

Specyfikacja każdego z t wierszy:

każdy wiersz składa się z dwóch liczb całkowitych n i z takich, że 1 < z ≤ 107, przy czym z jest zawsze liczbą pierwszą oraz 1 ≤ n ≤ 109.

Wyjście

Dla każdego zestawu testowego szukane p.

Przykład

Wejście:
1
10 5

Wyjście:
2

Dodane przez:Marcin Kasprowicz
Data dodania:2015-07-15
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.