시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1 1 1 100.000%

문제

숫자들의 집합 S0에 대해서 아래 알고리즘을 수행하자.

1: Counter = 0
2: Let S’ = set of all exclusive-or values between all possible number pairs in S
3: if S=S’ goto done
4: Else S = S∪S’, counter = counter+1 and goto step 2.
done: print the value of counter.

만약 S0 = {1, 2, 4}인 경우 이 알고리즘은 다음과 같이 돌아간다.

  • L1 이후 상태 : counter = 0, S = {1, 2, 4}
  • L1~L4를 한 번 수행한 후 상태 : S' = {3, 5, 6}, S = {1, 2, 3, 4, 5, 6}, counter = 1.
  • L2~L4를 한 번 더 수행한 후 상태 : S' = {1, 2, 3, 4, 5, 6, 7}, S = {1, 2, 3, 4, 5, 6, 7}, counter = 2.
  • L2~L3을 한 번 더 수행한 후 상태 : S' = {1, 2, 3, 4, 5, 6, 7}. S==S' 이므로 done으로 점프하여 2를 출력하고 프로그램이 끝난다.

S0이 주어졌을 때 주어진 알고리즘이 돌아간 후 counter의 값을 구하는 프로그램을 작성하여라.

입력

첫 번째 줄에는 테스트 케이스의 수를 나타내는 양의 정수 T가 주어진다. (T ≤ 100,000)

각 테스트 케이스는 두 개의 줄로 표현된다. 첫 번째 줄에는 초기 집합 S0의 크기 N이 주어진다. (1 ≤ N ≤ 50) 두 번째 줄에는 집합 S0의 원소에 해당되는 N개의 정수가 주어진다. 모든 원소는 1 이상 500,000 이하이며, 모두 다르다.

출력

각 테스트 케이스별로, 한 줄에 하나씩 'Case #x: R'과 같은 형식으로 출력한다. x는 테스트 케이스의 번호(1부터 시작)를 의미하며, R은 출력되는 counter의 값을 의미한다.

예제 입력 1

10
5
9 16 17 21 20
6
15 18 27 6 21 7
7
9 25 22 10 12 34 33
8
27 22 5 15 25 13 8 31
9
19 4 15 25 21 18 9 22 20
5
33 34 37 36 24
6
4 15 6 14 8 16
7
16 27 41 19 10 26 20
8
16 20 13 11 12 3 24 6
9
24 6 44 35 22 1 26 21 17

예제 출력 1

Case #1: 2
Case #2: 1
Case #3: 2
Case #4: 2
Case #5: 2
Case #6: 4
Case #7: 3
Case #8: 4
Case #9: 2
Case #10: 3

힌트

W3sicHJvYmxlbV9pZCI6Ijk3MjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJYT1IiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzIyYlx1Yzc5MFx1YjRlNFx1Yzc1OCBcdWM5ZDFcdWQ1NjkgUzBcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1YzU0NFx1Yjc5OCBcdWM1NGNcdWFjZTBcdWI5YWNcdWM5OThcdWM3NDQgXHVjMjE4XHVkNTg5XHVkNTU4XHVjNzkwLjxcL3A+XHJcblxyXG48cHJlPlxyXG4xOiBDb3VudGVyID0gMFxyXG4yOiBMZXQgUyZyc3F1bzsgPSBzZXQgb2YgYWxsIGV4Y2x1c2l2ZS1vciB2YWx1ZXMgYmV0d2VlbiBhbGwgcG9zc2libGUgbnVtYmVyIHBhaXJzIGluIFNcclxuMzogaWYgUz1TJnJzcXVvOyBnb3RvIGRvbmVcclxuNDogRWxzZSBTID0gUyZjdXA7UyZyc3F1bzssIGNvdW50ZXIgPSBjb3VudGVyKzEgYW5kIGdvdG8gc3RlcCAyLlxyXG5kb25lOiBwcmludCB0aGUgdmFsdWUgb2YgY291bnRlci48XC9wcmU+XHJcblxyXG48cD5cdWI5Y2NcdWM1N2QgUzAgPSB7MSwgMiwgNH1cdWM3NzggXHVhY2JkXHVjNmIwIFx1Yzc3NCBcdWM1NGNcdWFjZTBcdWI5YWNcdWM5OThcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWIzY2NcdWM1NDRcdWFjMDRcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+TDEgXHVjNzc0XHVkNmM0IFx1YzBjMVx1ZDBkYyA6IGNvdW50ZXIgPSAwLCBTID0gezEsIDIsIDR9PFwvbGk+XHJcblx0PGxpPkwxfkw0XHViOTdjIFx1ZDU1YyBcdWJjODggXHVjMjE4XHVkNTg5XHVkNTVjIFx1ZDZjNCBcdWMwYzFcdWQwZGMgOiBTJiMzOTsgPSB7MywgNSwgNn0sIFMgPSB7MSwgMiwgMywgNCwgNSwgNn0sIGNvdW50ZXIgPSAxLjxcL2xpPlxyXG5cdDxsaT5MMn5MNFx1Yjk3YyBcdWQ1NWMgXHViYzg4IFx1YjM1NCBcdWMyMThcdWQ1ODlcdWQ1NWMgXHVkNmM0IFx1YzBjMVx1ZDBkYyA6IFMmIzM5OyA9IHsxLCAyLCAzLCA0LCA1LCA2LCA3fSwgUyA9IHsxLCAyLCAzLCA0LCA1LCA2LCA3fSwgY291bnRlciA9IDIuPFwvbGk+XHJcblx0PGxpPkwyfkwzXHVjNzQ0IFx1ZDU1YyBcdWJjODggXHViMzU0IFx1YzIxOFx1ZDU4OVx1ZDU1YyBcdWQ2YzQgXHVjMGMxXHVkMGRjIDogUyYjMzk7ID0gezEsIDIsIDMsIDQsIDUsIDYsIDd9LiBTPT1TJiMzOTsgXHVjNzc0XHViYmMwXHViODVjIGRvbmVcdWM3M2NcdWI4NWMgXHVjODEwXHVkNTA0XHVkNTU4XHVjNWVjIDJcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc3NCBcdWIwNWRcdWIwOWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+UzBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzc0IFx1YjNjY1x1YzU0NFx1YWMwNCBcdWQ2YzQgY291bnRlclx1Yzc1OCBcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKFQgJmxlOyAxMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzkwNFx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWI0MWNcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2QwOFx1YWUzMCBcdWM5ZDFcdWQ1NjkgUzBcdWM3NTggXHVkMDZjXHVhZTMwIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyA1MCkgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjOWQxXHVkNTY5IFMwXHVjNzU4IFx1YzZkMFx1YzE4Y1x1YzVkMCBcdWQ1NzRcdWIyZjlcdWI0MThcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjNmQwXHVjMThjXHViMjk0IDEgXHVjNzc0XHVjMGMxIDUwMCwwMDAgXHVjNzc0XHVkNTU4XHVjNzc0XHViYTcwLCBcdWJhYThcdWI0NTAgXHViMmU0XHViOTc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViY2M0XHViODVjLCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSAmIzM5O0Nhc2UgI3g6IFImIzM5O1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVkNjE1XHVjMmRkXHVjNzNjXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4geFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YmM4OFx1ZDYzOCgxXHViZDgwXHVkMTMwIFx1YzJkY1x1Yzc5MSlcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTU4XHViYTcwLCBSXHVjNzQwIFx1Y2Q5Y1x1YjgyNVx1YjQxOFx1YjI5NCBjb3VudGVyXHVjNzU4IFx1YWMxMlx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTcyOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlhPUiIsImRlc2NyaXB0aW9uIjoiPHA+R2l2ZW4gYSBzZXQgb2YgbnVtYmVycyBTLCBjb25zaWRlciB0aGUgZm9sbG93aW5nIGFsZ29yaXRobS48XC9wPlxyXG5cclxuPHByZT5cclxuMTogQ291bnRlciA9IDBcclxuMjogTGV0IFMmcnNxdW87ID0gc2V0IG9mIGFsbCBleGNsdXNpdmUtb3IgdmFsdWVzIGJldHdlZW4gYWxsIHBvc3NpYmxlIG51bWJlciBwYWlycyBpbiBTXHJcbjM6IGlmIFM9UyZyc3F1bzsgZ290byBkb25lXHJcbjQ6IEVsc2UgUyA9IFMmY3VwO1MmcnNxdW87LCBjb3VudGVyID0gY291bnRlcisxIGFuZCBnb3RvIHN0ZXAgMi5cclxuZG9uZTogcHJpbnQgdGhlIHZhbHVlIG9mIGNvdW50ZXIuPFwvcHJlPlxyXG5cclxuPHA+R2l2ZW4gUywgeW91ciB0YXNrIGlzIHRvIGNhbGN1bGF0ZSB0aGUgdmFsdWUgb2YgdGhlIGNvdW50ZXIgYWZ0ZXIgdGhlIHByb2dyYW0gc3RvcHMuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+Rm9yIGV4YW1wbGUgaWYgUyA9IHsxLDIsNH08XC9saT5cclxuXHQ8bGk+VGhlbiBhZnRlciBzdGVwIDE6IFMmcnNxdW87ID0gezMsNSw2fSBhbmQgUyA9IHsxLDIsMyw0LDUsNn0sIGNvdW50ZXIgPSAxPFwvbGk+XHJcblx0PGxpPkFmdGVyIHN0ZXAgMjogUyZyc3F1bzsgPSB7MSwyLDMsNCw1LDYsN30gYW5kIFMgPSB7MSwyLDMsNCw1LDYsN30sIGNvdW50ZXIgPSAyPFwvbGk+XHJcblx0PGxpPkFmdGVyIHN0ZXAgMzogUyZyc3F1bzsgPSB7MSwyLDMsNCw1LDYsN308XC9saT5cclxuXHQ8bGk+Tm93IG5vIG5ldyBudW1iZXIgaXMgZ2VuZXJhdGVkLiBTbywgd2UgY2FuIG91dHB1dCB0aGUgZmluYWwgdmFsdWUgb2YgY291bnRlciwgd2hpY2ggaXMgMi4mbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgaGFzIGEgcG9zaXRpdmUgaW50ZWdlciBULCBUICZsdDs9IDEwMCwwMDAsIGRlbm90aW5nIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gVGhpcyBpcyBmb2xsb3dlZCBieSBlYWNoIHRlc3QgY2FzZSBwZXIgbGluZS48XC9wPlxyXG5cclxuPHA+RWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgdHdvIGxpbmVzLiBUaGUgZmlyc3QgbGluZSBjb250YWlucyBOLCB0aGUgc2l6ZSBvZiB0aGUgc2V0LiBOIGlzIGJldHdlZW4gMSBhbmQgNTAgaW5jbHVzaXZlLiBUaGUgbmV4dCBsaW5lIGNvbnRhaW5zIHRoZSBOIGludGVnZXJzIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS4gVGhlc2UgTiBpbnRlZ2VycyBhcmUgdGhlIHNldCBTLiBBbGwgb2YgdGhlIGludGVnZXJzIGluIHRoZSBzZXQgYXJlIGJldHdlZW4gMSBhbmQgNTAwLDAwMCBpbmNsdXNpdmUsIGFuZCBkaXN0aW5jdC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHRoZSBvdXRwdXQgY29udGFpbnMgYSBsaW5lIGluIHRoZSBmb3JtYXQgQ2FzZSAjeDogUiwgd2hlcmUgeCBpcyB0aGUgY2FzZSBudW1iZXIgKHN0YXJ0aW5nIGZyb20gMSkgYW5kIFIgaXMgdGhlIGZpbmFsIHZhbHVlIG9mIHRoZSBjb3VudGVyLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==