문제
인덱스가 1ドル$부터 시작하는 길이 $n$의 수열 $B$가 있으며, 초기에 모든 인덱스 $k$에 대해 $B_k=k$입니다. 흐즈로는 이 수열에 할 수 있는 매우 이상하고 신기한 연산을 생각해 냈습니다. 그 연산은 다음과 같습니다.
- 어떠한 양의 정수 $k$가 주어질 때, $k$의 약수인 가장 큰 2ドル$의 거듭제곱수 $l$을 찾고, $k \neq l$이라면 $B_k$와 $B_l$을 서로 교환하는 동작을 $k$-교환이라고 합시다.
- $i$-교환을 $i=1,2,\cdots,n$에 대해 순서대로 반복합니다.
흐즈로는 이 연산을 이상한 섞기 연산이라고 부르기로 했습니다. 수열 $B$의 길이 $n$이 주어질 때, $B$에 이상한 섞기 연산을 수행한 뒤 원소 1ドル$이 있는 인덱스를 출력하세요. 다시 말해, 연산이 끝난 후 $B_j=1$이 되는 인덱스 $j$를 찾아 출력해야 합니다.
출력
각 테스트 케이스에 대해, 길이가 $n$인 수열 $B$에 이상한 섞기 연산을 수행한 뒤 원소 1ドル$이 있는 인덱스 $j$를 별도의 줄에 출력하세요.
$n=1$일 때, 1ドル$이 존재할 수 있는 위치는 1ドル$번째가 유일합니다. 따라서 정답은 1ドル$입니다.
$n=3$일 때, 이상한 섞기 연산이 끝난 후 $B$는 $[3,2,1]$이 됩니다. 이때 1ドル$은 3ドル$번째 인덱스에 존재합니다. 따라서 정답은 3ドル$입니다.
노트
본 문제에서 2ドル$의 거듭제곱수는 2ドル^k$ 꼴로 표현했을 때 $k$가 음이 아닌 정수가 되는 수로 정의됩니다.
W3sicHJvYmxlbV9pZCI6IjMxMjE1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNzc0XHVjMGMxXHVkNTVjIFx1YzExZVx1YWUzMCBcdWM1ZjBcdWMwYjAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Yzc3OFx1YjM3MVx1YzJhNFx1YWMwMCAkMSRcdWJkODBcdWQxMzAgXHVjMmRjXHVjNzkxXHVkNTU4XHViMjk0IFx1YWUzOFx1Yzc3NCAkbiRcdWM3NTggXHVjMjE4XHVjNWY0ICRCJFx1YWMwMCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1Y2QwOFx1YWUzMFx1YzVkMCBcdWJhYThcdWI0ZTAgXHVjNzc4XHViMzcxXHVjMmE0ICRrJFx1YzVkMCBcdWIzMDBcdWQ1NzQgJEJfaz1rJFx1Yzc4NVx1YjJjOFx1YjJlNC4gXHVkNzUwXHVjOTg4XHViODVjXHViMjk0IFx1Yzc3NCBcdWMyMThcdWM1ZjRcdWM1ZDAgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViOWU0XHVjNmIwIFx1Yzc3NFx1YzBjMVx1ZDU1OFx1YWNlMCBcdWMyZTBcdWFlMzBcdWQ1NWMgXHVjNWYwXHVjMGIwXHVjNzQ0IFx1YzBkZFx1YWMwMVx1ZDU3NCBcdWIwYzhcdWMyYjVcdWIyYzhcdWIyZTQuIFx1YWRmOCBcdWM1ZjBcdWMwYjBcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YzJiNVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWM1YjRcdWI1YTBcdWQ1NWMgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCAkayRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YywgJGskXHVjNzU4IFx1YzU3ZFx1YzIxOFx1Yzc3OCBcdWFjMDBcdWM3YTUgXHVkMDcwICQyJFx1Yzc1OCBcdWFjNzBcdWI0ZWRcdWM4MWNcdWFjZjFcdWMyMTggJGwkXHVjNzQ0IFx1Y2MzZVx1YWNlMCwgJGsgXFxuZXEgbCRcdWM3NzRcdWI3N2NcdWJhNzQgJEJfayRcdWM2NDAgJEJfbCRcdWM3NDQgXHVjMTFjXHViODVjIFx1YWQ1MFx1ZDY1OFx1ZDU1OFx1YjI5NCBcdWIzZDlcdWM3OTFcdWM3NDQgPHN0cm9uZz4kayQtXHVhZDUwXHVkNjU4PFwvc3Ryb25nPlx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NjlcdWMyZGNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPjxzdHJvbmc+JGkkLVx1YWQ1MFx1ZDY1ODxcL3N0cm9uZz5cdWM3NDQgJGk9MSwyLFxcY2RvdHMsbiRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWJjMThcdWJjZjVcdWQ1NjlcdWIyYzhcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVkNzUwXHVjOTg4XHViODVjXHViMjk0IFx1Yzc3NCBcdWM1ZjBcdWMwYjBcdWM3NDQgPHN0cm9uZz5cdWM3NzRcdWMwYzFcdWQ1NWMgXHVjMTFlXHVhZTMwIFx1YzVmMFx1YzBiMDxcL3N0cm9uZz5cdWM3NzRcdWI3N2NcdWFjZTAgXHViZDgwXHViOTc0XHVhZTMwXHViODVjIFx1ZDU4OFx1YzJiNVx1YjJjOFx1YjJlNC4gXHVjMjE4XHVjNWY0ICRCJFx1Yzc1OCBcdWFlMzhcdWM3NzQgJG4kXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGMsICRCJFx1YzVkMCA8c3Ryb25nPlx1Yzc3NFx1YzBjMVx1ZDU1YyBcdWMxMWVcdWFlMzAgXHVjNWYwXHVjMGIwPFwvc3Ryb25nPlx1Yzc0NCBcdWMyMThcdWQ1ODlcdWQ1NWMgXHViNGE0IFx1YzZkMFx1YzE4YyAkMSRcdWM3NzQgXHVjNzg4XHViMjk0IFx1Yzc3OFx1YjM3MVx1YzJhNFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWMxMzhcdWM2OTQuIFx1YjJlNFx1YzJkYyBcdWI5ZDBcdWQ1NzQsIFx1YzVmMFx1YzBiMFx1Yzc3NCBcdWIwNWRcdWIwOWMgXHVkNmM0ICRCX2o9MSRcdWM3NzQgXHViNDE4XHViMjk0IFx1Yzc3OFx1YjM3MVx1YzJhNCAkaiRcdWI5N2MgXHVjYzNlXHVjNTQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzU3YyBcdWQ1NjlcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCAkVCRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LiAoJDEgXFxsZSBUIFxcbGUgMTAwMCQpPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWJkODBcdWQxMzAgXHVjZDFkICRUJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzAxXHVhYzAxICRCJFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YzIxOCAkbiRcdWM3NzQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LiAoJDEgXFxsZSBuIFxcbGUgMTBeOSQpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0LCBcdWFlMzhcdWM3NzRcdWFjMDAgJG4kXHVjNzc4IFx1YzIxOFx1YzVmNCAkQiRcdWM1ZDA8c3Ryb25nPiBcdWM3NzRcdWMwYzFcdWQ1NWMgXHVjMTFlXHVhZTMwIFx1YzVmMFx1YzBiMDxcL3N0cm9uZz5cdWM3NDQgXHVjMjE4XHVkNTg5XHVkNTVjIFx1YjRhNCBcdWM2ZDBcdWMxOGMgJDEkXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWM3NzhcdWIzNzFcdWMyYTQgJGokXHViOTdjIFx1YmNjNFx1YjNjNFx1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVjZDljXHViODI1XHVkNTU4XHVjMTM4XHVjNjk0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWJjZjggXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjICQyJFx1Yzc1OCBcdWFjNzBcdWI0ZWRcdWM4MWNcdWFjZjFcdWMyMThcdWIyOTQgJDJeayQgXHVhZjM0XHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU4OFx1Yzc0NCBcdWI1NGMgJGskXHVhYzAwIFx1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4XHVhYzAwIFx1YjQxOFx1YjI5NCBcdWMyMThcdWI4NWMgXHVjODE1XHVjNzU4XHViNDI5XHViMmM4XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPiRuPTEkXHVjNzdjIFx1YjU0YywgJDEkXHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzcwNFx1Y2U1OFx1YjI5NCAkMSRcdWJjODhcdWM5ZjhcdWFjMDAgXHVjNzIwXHVjNzdjXHVkNTY5XHViMmM4XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMgXHVjODE1XHViMmY1XHVjNzQwICQxJFx1Yzc4NVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+JG49MyRcdWM3N2MgXHViNTRjLCA8c3Ryb25nPlx1Yzc3NFx1YzBjMVx1ZDU1YyBcdWMxMWVcdWFlMzAgXHVjNWYwXHVjMGIwPFwvc3Ryb25nPlx1Yzc3NCBcdWIwNWRcdWIwOWMgXHVkNmM0ICRCJFx1YjI5NCAkWzMsMiwxXSRcdWM3NzQgXHViNDI5XHViMmM4XHViMmU0LiBcdWM3NzRcdWI1NGMgJDEkXHVjNzQwICQzJFx1YmM4OFx1YzlmOCBcdWM3NzhcdWIzNzFcdWMyYTRcdWM1ZDAgXHVjODc0XHVjN2FjXHVkNTY5XHViMmM4XHViMmU0LiZuYnNwO1x1YjUzMFx1Yjc3Y1x1YzExYyBcdWM4MTVcdWIyZjVcdWM3NDAgJDMkXHVjNzg1XHViMmM4XHViMmU0LjxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjMxMjE1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3RyYW5nZSBTaHVmZmxlIiwiZGVzY3JpcHRpb24iOiI8cD5UaGVyZSBpcyBhICQxJC1pbmRleGVkJm5ic3A7c2VxdWVuY2UgJEIkIG9mIGxlbmd0aCAkbiQsIHdoZXJlIGluaXRpYWxseSAkQl9rPWskIGhvbGRzIGZvciBldmVyeSBpbmRleCAkayQuIENocm9tYXRlIGhhcyBjb21lIHVwIHdpdGggYSB2ZXJ5IHN0cmFuZ2UgYW5kIGludGVyZXN0aW5nIHR5cGUgb2Ygb3BlcmF0aW9uIHRoYXQgY2FuIGJlIGRvbmUgb24gdGhlIHNlcXVlbmNlLiBUaGUgb3BlcmF0aW9uIGlzIGRlZmluZWQgYXMgZm9sbG93cy48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5HaXZlbiBzb21lIHBvc2l0aXZlIGludGVnZXIgJGskLCBsZXQgdXMgZGVmaW5lICRsJCBhcyBsYXJnZXN0IHBvd2VyIG9mICQyJCB3aGljaCBpcyBhIGRpdmlzb3Igb2YgJGskLiBUaGVuLCBzd2FwICRCX2skIGFuZCAkQl9sJCBpZiAkayBcXG5lcSBsJC4gV2Ugd2lsbCBjYWxsIHRoaXMgdGhlIDxzdHJvbmc+JGskLXN3YXA8XC9zdHJvbmc+LjxcL2xpPlxyXG5cdDxsaT5QZXJmb3JtIDxzdHJvbmc+JGkkLXN3YXA8XC9zdHJvbmc+Jm5ic3A7Zm9yIGFsbCAkaT0xLDIsXFxjZG90cyxuJCBpbiB0aGlzIGV4YWN0IG9yZGVyLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkNocm9tYXRlIGhhcyBkZWNpZGVkIHRvIGNhbGwgdGhpcyBvcGVyYXRpb24gdGhlIDxzdHJvbmc+U3RyYW5nZSBTaHVmZmxlPFwvc3Ryb25nPi4gR2l2ZW4gJG4kLCB0aGUgbGVuZ3RoIG9mIHRoZSBzZXF1ZW5jZSAkQiQsIHBsZWFzZSBmaW5kIHRoZSBpbmRleCBvZiB0aGUgZWxlbWVudCAkMSQgYWZ0ZXIgcGVyZm9ybWluZyB0aGUgPHN0cm9uZz5TdHJhbmdlIFNodWZmbGU8XC9zdHJvbmc+Jm5ic3A7b24gJEIkLiBGb3JtYWxseSwgZmluZCB0aGUgaW5kZXggJGokIHN1Y2ggdGhhdCAkQl9qPTEkIGFmdGVyIHRoZSBvcGVyYXRpb24gaGFzIGZpbmlzaGVkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzICRUJC4gKCQxIFxcbGUgVCBcXGxlIDEwMDAkKTxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgJFQkIGxpbmVzIGNvbnRhaW4gYSBzaW5nbGUgaW50ZWdlciAkbiQgJm1kYXNoOyB0aGUgbGVuZ3RoIG9mIHRoZSBzZXF1ZW5jZSAkQiQuICgkMSBcXGxlIG4gXFxsZSAxMF45JCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UgZ2l2ZW4sIG91dHB1dCBhIHNpbmdsZSBpbnRlZ2VyICRqJCAmbWRhc2g7IHRoZSBpbmRleCBvZiB0aGUgZWxlbWVudCAkMSQgYWZ0ZXIgcGVyZm9ybWluZyB0aGUgPHN0cm9uZz5TdHJhbmdlIFNodWZmbGU8XC9zdHJvbmc+Jm5ic3A7Jm1kYXNoOyBvbiBhIHNlcGFyYXRlIGxpbmUuPFwvcD5cclxuIiwiaGludCI6IjxwPkluIHRoaXMgdGFzaywgcG93ZXJzIG9mICQyJCBhcmUgZGVmaW5lZCBhcyBpbnRlZ2VycyBpbiB0aGUgZm9ybSBvZiAkMl5rJCwgc3VjaCB0aGF0ICRrJCBpcyBhIG5vbm5lZ2F0aXZlIGludGVnZXIuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPldoZW4gJG49MSQsIHRoZSBlbGVtZW50ICQxJCBjYW4gb25seSBleGlzdCBvbiBpbmRleCAkMSQuIFRoZSBhbnN3ZXIgaXMgdGhlcmVmb3JlICQxJC48XC9wPlxyXG5cclxuPHA+V2hlbiAkbj0zJCwgJEIkIGJlY29tZXMgJFszLDIsMV0kIGFmdGVyIHRoZSA8c3Ryb25nPlN0cmFuZ2UgU2h1ZmZsZTxcL3N0cm9uZz4gaXMgZmluaXNoZWQuIEhlcmUsIHRoZSBlbGVtZW50ICQxJCBsaWVzIG9uIGluZGV4ICQzJC4gVGhlIGFuc3dlciBpcyB0aGVyZWZvcmUgJDMkLjxcL3A+XHJcbiJ9XQ==