今天是贝茜的生日，为了庆祝自己的生日，贝茜邀你来玩一个游戏。

贝茜让 N (1\leq N\leq 10^5) 头奶牛坐成一个圈。除了 1 号与 N 号奶牛外，i 号奶牛与 i-1 号和 i+1 号奶牛相邻。N 号奶牛与 1 号奶牛相邻。农夫约翰用很多纸条装满了一个桶，每一张包含了一个不一定是独一无二的 1 到 10^6 的数字。

接着每一头奶牛 i 从桶中取出一张纸条 A_i。每头奶牛轮流走上一圈，同时拍打所有手上数字能整除在自己纸条上的数字的牛的头，然后坐回到原来的位置。牛们希望你帮助他们确定，每一头奶牛需要拍打的牛的数量。

第一行一个整数N

然后是N个数字，表示奶牛手里的纸条上的数字

每只奶牛需要拍打的数量