Fan Li

Fan Li (范蠡) was an ancient Chinese advisor in the state of Yue in the Spring and Autumn period. He is a successful militarist and a successful business man. He is one of the main characters of a famous Chinese proverb “卧薪尝胆”. One day, when he was training the army, he came up with an idea, if he let all the soldiers stand in a line (every soldier has a fighting capacity), what is the maximum disjoint intervals he can choose so that the greatest common divisor of all the intervals are equal, and how many ways can he choose the maximum disjoint intervals satisfy the condition. The different ways may be very large, output the answer mod 998244353.

There are multiple test cases.
Each test cases begins with an integer n, then followed n positive integers.
1 <= n <= 100000
All the integers are less than 2333333.

For each test case, output the number of maximum intervals and the ways of reach the maximum number.

3
1 2 3
5
1 2 2 2 2
3
1 2 1

2 1
4 1
2 3

ZSTU

2015 Multi-University Training Contest 3