Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Battle in Byteland

Limits 1s, 512 MB

There will be a gaming competition in Byteland, the winner will get a pair of shoes. With these shoes, you can teleport anywhere. Since Byteland has a lot of traffic issues, Alal decides to win these shoes. Any team can participate in the competition , its not necessary that all team has equal members. All participants are given an unique ID. A participant belongs to a team if there is at least one other member that GCD of their ID is greater than 1. If a participants ID is x, he belongs to a team if there is at least one participant whose ID is y and GCD(x,y)>1. GCD means Greatest Common Divisor. Alal hacked into the system and found the IDs of all participants including him. He is tired and asked for your help. You have to find out how many teams are participating in the competition and how many member Alal’s team has.

Input

you will be given an integer n, the number of participants. There will be n integers describing the ID of i’th participant, x. Alal’s ID is the first one.

1<=n<=1000

2<=x<=1000000000

Output

Print the number of teams participating and the number of member Alal’s team has.

Samples

InputOutput
7
2 5 3 6 15 7 49
2 5

In the Sample test, there are two teams. One contains 2,3,5,6,15 and Other contains 7,49. Alal’s ID is 2, so his team has 5 members.

Discussion