One and Zero are good freinds who like playing new games. One day they bought two deck of cards. Each deck had equal number of cards in it and on every card there was a number printed on it. They decided to play a game in which they would draw one card from each deck such that the numbers on them are not co-prime (have atleast one common factor other than 1).

For example, if two decks are A and B each having n cards, then firstly Zero will draw (A_i , B_j) such that A_i and B_j are not co-prime. Then One will do the same. And so on.

Your task is to maximize such pairs that can be drawn from A and B. Also find who will draw the last pair, Player 0 or Player 1.

Note: Zero will always start the game followed by One and then it goes on alternately untill it is not possible to draw more cards without violating the rule of game.

Input Format

The first line contains an integer n, which is number of cards in each deck. 2 lines follow, each line containing n numbers separated by a single space in which first line contains numbers written on cards of deck A and second line contains numbers written on cards of deck B. The format is shown below.n

n

A[0] A[1] ...... A[n-1]

B[0] B[1] ...... B[n-1]

Constraints

0 < n <= 10⁵ 
2 <= A[i], B[i] <= 10⁹ 
Each number written on cards in both decks are generated randomly between 2 and 10⁹

Output Format

Output an integer S, i.e. maximum possible number of such draws.

In next line output 'Player 0' if Zero will draw the last pair, else 'Player 1' (without quotes).

Sample Input

4

2 5 6 7

4 9 10 12

Sample Output

3

Player 0

Explanation

You can remove: 

(2, 4) - Player Zero

(5, 10) - Player One

(6, 9) - Player Zero

Hence 3 and Player 0.