K2 - Ka-Ching 2

Časový limit: 2s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Alica sa dostala k nepredstaviteľnému bohatstvu B. Problém? Dozvedeli sa o tom jej známi a každý chce kúsok. Keďže sa však nejedná o kadejaké peniaze, so zdieľaním sú problémy. V momente, keď sa Alica rozhodne niekoho obdarovať, jej bohatstvo klesne podľa veľmi divného vzorca:

b' = X^b % b

kde b je jej bohatstvo pred a b' po rozdelení; % predstavuje operáciu modulo, zvyšok po delení. (To ale neznamená, že rozdiel dostane obdarovaný)
Vyzerá to tak, že po istom počte obdarovaní sa Alica ocitne na mizine ... a to by nechcela. Akákoľvek nenulová hodnota je však stále viac, než je schopná za svoj život minúť a tak je ochotná sa deliť dovtedy, kým by ju to nezruinovalo. Zistite, koľko najviac ľudí môže obdarovať.

Úloha

Pre dané B a X zistite, s koľkými ľuďmi sa Alica môže podeliť.

Vstup

V prvom riadku súboru sa nachádza číslo Q udávajúce počet sád.

Nasleduje Q riadkov s dvojicou čísel X a B.

1 ≤ Q ≤ 100
2 ≤ X ≤ 1337

K1

1 ≤ B ≤ 1000

K2

1 ≤ B ≤ 10⁹

Výstup

Výstupom programu je výsledok pre každú sadu na samostatnom riadku.

Príklad

Vstup:

Výstup:

1
2
0

14 Domáce 1