Дельфіни

Весна… Кролики радіють сонечку, небо стало добрим і м'яким, з'явились квіти, дельфіни прилетіли з теплих країв.

Справді! Дельфіни для кроликів — символ весни. Адже вони так чудово співають, літають, кружляють. Така поведінка дельфінів тішить майже всіх. Майже… Вченим кроликам з Інституту контролю за популяцією дельфінів у верхівках дерев Кроляндії радісна пора підкидає купу роботи. Їм потрібно контролювати цілі зграї дельфінів. Але вони сподіваються, що ми розробимо для них алгоритм прогнозування популяцій дельфінів у верхівках дерев.

Отже, потрібно написати програму, яка визначає імовірні позиції дельфінів. Спочатку буде задано опис $N$ дельфінів. Усього потрібно слідкувати за $M$ деревами. Кожен дельфін спочатку сидить на верхівці якогось дерева. Кожен дельфін за одну секунду з однаковою імовірністю може перелетіти на будь-яке дерево з номером, взаємно простим із номером того дерева, на якому він сидів (взаємно прості числа мають найбільший спільний дільник, що дорівнює $1$), або залишитися на місці. Таким чином, якщо дерев $6$, і дельфін сидить на дереві з номером $3$, то події "дельфін через секунду буде на дереві з номером $1$ (або $2$, $3$, $4$, $5$)" — рівноможливі.

Для перевірки того, що ваш алгоритм правильний, виведіть суму математичних сподівань кількості дельфінів на деревах (через $T$ секунд). Тобто, якщо m_1, m_2, ..., m_M — математичні сподівання кількості дельфінів відповідно на першому, другому, ..., $M$-му дереві, то потрібно обчислити