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 (Ai , Bj) such that Ai and Bj 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.

Constraints

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

Problem Link : https://www.hackerearth.com/challenge/college/ietcodearena/algorithm/special-pairs-5-3347a9bf/

Any hint for arriving at the solution would be appreciated.

Thanks in advance :)