Майк — бармен в баре Рико. В заведении Рико пивные стаканы кладутся на особую полку. Всего в баре n сортов пива, пронумерованных от 1 до n. Бокал с i-м сортом пива содержит ai миллилитров пены.
Максим — босс Майка. Сегодня он сказал Майку выполнить q запросов. Изначально полка пустая. Каждый запрос представляет собой целое число x. Если пиво номер x уже есть на полке, то Майк должен забрать его с полки, в противном случае — положить его на полку.
После каждого запроса Майк должен определить качество полки. Медведи — те ещё гики, так что они считают, что качество полки — это количество пар (i, j) стаканов на полке, таких, что i < j и 
, где 
— наибольший общий делитель чисел a и b.
Майк устал. Поэтому он попросил вам помочь ему выполнить эти запросы.
Выходные данные
Для каждого запроса выведите ответ в отдельной строке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 6
1 2 3 4 6
1
2
3
4
5
1
|
0
1
3
5
6
2
|