시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 33 12 9 56.250%

문제

길이 n인 음이 아닌 정수로 이루어진 배열 A에 대해, 0개 이상의 원소를 지워서 얻을 수 있는 배열을 "부분열"라고 한다.

배열 A의 부분열 S에 대해, S가 다음 조건을 만족하면 S를 A의 "홀수 부분열"이라고 정의한다:

  • S의 원소의 합의 자릿수 중 홀수인 것들이 홀수이다.

음이 아닌 정수 배열 A를 입력받아 A의 서로 다른 홀수 부분열의 개수를 출력하시오. 단, 부분열의 원소들을 정렬했을 시 그 결과가 같다면 같은 부분열로 취급한다.

A = [3, 3, 6, 8, 6] 경우 정답은 8이다.

  • 길이가 0인 홀수 부분열: X
  • 길이가 1인 홀수 부분열: [3]
    • 합이 3, 자릿수 중 홀수가 3으로 하나
  • 길이가 2인 홀수 부분열: [3, 6], [6, 6], [6, 8]
    • 합이 각각 9, 12, 14로 자릿수 중 홀수가 9, 1, 1로 하나씩
  • 길이가 3인 홀수 부분열: [3, 3, 6], [3, 3, 8]
  • 길이가 4인 홀수 부분열: [3, 3, 6, 6], [3, 6, 6, 8]
  • 길이가 5인 홀수 부분열: X

입력

첫 줄에 테스트 케이스의 수 T가 주어진다 (1 ≤ T ≤ 10).

각 테스트 케이스에 대해 첫 줄에 A의 길이 n 이 주어진다. 둘째 줄에 n개의 0이상의 정수가 공백으로 구분되어 주어진다. A의 각 원소는 0 이상 2,000 이하이다.

출력

각 테스트 케이스에 대해 홀수 부분열의 수를 한 줄에 출력한다.

서브태스크 1 (3점)

  • 1 ≤ n ≤ 10

서브태스크 2 (11점)

  • 1 ≤ n ≤ 60

예제 입력 1

3
3
3 3 6
4
0 1 2 3
5
3 3 6 8 6

예제 출력 1

3
8
8

힌트

  • 테스트 케이스 1: {3}, {3,6}, {3, 3, 6} 세 종류의 홀수-부분열이 있다.
  • 테스트 케이스 2: {1}, {3}, {0,1}, {0,3}, {1,2}, {2,3}, {0,1,2}, {0,2,3} 여덟 종류의 홀수-부분열이 있다.
  • 테스트 케이스 3: 문제에서 서술된대로 여덟 종류의 홀수-부분열이 있다.
W3sicHJvYmxlbV9pZCI6IjE3Mjc5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNjQwXHVjMjE4IFx1YmQ4MFx1YmQ4NFx1YzVmNCIsImRlc2NyaXB0aW9uIjoiPHA+XHVhZTM4XHVjNzc0IG5cdWM3NzggXHVjNzRjXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWM4MTVcdWMyMThcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmMzMFx1YzVmNCBBXHVjNWQwIFx1YjMwMFx1ZDU3NCwmbmJzcDswXHVhYzFjIFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWM2ZDBcdWMxOGNcdWI5N2MgXHVjOWMwXHVjNmNjXHVjMTFjIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmMzMFx1YzVmNFx1Yzc0NCAmcXVvdDtcdWJkODBcdWJkODRcdWM1ZjQmcXVvdDtcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJjMzBcdWM1ZjQgQVx1Yzc1OCBcdWJkODBcdWJkODRcdWM1ZjQgU1x1YzVkMCBcdWIzMDBcdWQ1NzQsIFNcdWFjMDAgXHViMmU0XHVjNzRjIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWJhNzQgU1x1Yjk3YyBBXHVjNzU4ICZxdW90O1x1ZDY0MFx1YzIxOCBcdWJkODBcdWJkODRcdWM1ZjQmcXVvdDtcdWM3NzRcdWI3N2NcdWFjZTAgXHVjODE1XHVjNzU4XHVkNTVjXHViMmU0OjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlNcdWM3NTggXHVjNmQwXHVjMThjXHVjNzU4IFx1ZDU2OVx1Yzc1OCBcdWM3OTBcdWI5YmZcdWMyMTggXHVjOTExIFx1ZDY0MFx1YzIxOFx1Yzc3OCBcdWFjODNcdWI0ZTRcdWM3NzQgXHVkNjQwXHVjMjE4XHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4IFx1YmMzMFx1YzVmNCBBXHViOTdjIFx1Yzc4NVx1YjgyNVx1YmMxYlx1YzU0NCBBXHVjNzU4IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVkNjQwXHVjMjE4IFx1YmQ4MFx1YmQ4NFx1YzVmNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVjMmRjXHVjNjI0LiBcdWIyZTgsIFx1YmQ4MFx1YmQ4NFx1YzVmNFx1Yzc1OCBcdWM2ZDBcdWMxOGNcdWI0ZTRcdWM3NDQgXHVjODE1XHViODJjXHVkNTg4XHVjNzQ0IFx1YzJkYyBcdWFkZjggXHVhY2IwXHVhY2ZjXHVhYzAwIFx1YWMxOVx1YjJlNFx1YmE3NCBcdWFjMTlcdWM3NDAgXHViZDgwXHViZDg0XHVjNWY0XHViODVjIFx1Y2RlOFx1YWUwOVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+QSA9IFszLCAzLCA2LCA4LCA2XSBcdWFjYmRcdWM2YjAgXHVjODE1XHViMmY1XHVjNzQwIDhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVhZTM4XHVjNzc0XHVhYzAwIDBcdWM3NzggXHVkNjQwXHVjMjE4IFx1YmQ4MFx1YmQ4NFx1YzVmNDogWDxcL2xpPlxyXG5cdDxsaT5cdWFlMzhcdWM3NzRcdWFjMDAgMVx1Yzc3OCBcdWQ2NDBcdWMyMTggXHViZDgwXHViZDg0XHVjNWY0OiBbM11cclxuXHQ8dWw+XHJcblx0XHQ8bGk+XHVkNTY5XHVjNzc0IDMsIFx1Yzc5MFx1YjliZlx1YzIxOCBcdWM5MTEgXHVkNjQwXHVjMjE4XHVhYzAwIDNcdWM3M2NcdWI4NWMgXHVkNTU4XHViMDk4PFwvbGk+XHJcblx0PFwvdWw+XHJcblx0PFwvbGk+XHJcblx0PGxpPlx1YWUzOFx1Yzc3NFx1YWMwMCAyXHVjNzc4IFx1ZDY0MFx1YzIxOCBcdWJkODBcdWJkODRcdWM1ZjQ6IFszLCA2XSwgWzYsIDZdLCBbNiwgOF1cclxuXHQ8dWw+XHJcblx0XHQ8bGk+XHVkNTY5XHVjNzc0IFx1YWMwMVx1YWMwMSA5LCAxMiwgMTRcdWI4NWMgXHVjNzkwXHViOWJmXHVjMjE4IFx1YzkxMSBcdWQ2NDBcdWMyMThcdWFjMDAgOSwgMSwgMVx1Yjg1YyBcdWQ1NThcdWIwOThcdWM1Mjk8XC9saT5cclxuXHQ8XC91bD5cclxuXHQ8XC9saT5cclxuXHQ8bGk+XHVhZTM4XHVjNzc0XHVhYzAwIDNcdWM3NzggXHVkNjQwXHVjMjE4IFx1YmQ4MFx1YmQ4NFx1YzVmNDogWzMsIDMsIDZdLCBbMywgMywgOF08XC9saT5cclxuXHQ8bGk+XHVhZTM4XHVjNzc0XHVhYzAwIDRcdWM3NzggXHVkNjQwXHVjMjE4IFx1YmQ4MFx1YmQ4NFx1YzVmNDogWzMsIDMsIDYsIDZdLCBbMywgNiwgNiwgOF08XC9saT5cclxuXHQ8bGk+XHVhZTM4XHVjNzc0XHVhYzAwIDVcdWM3NzggXHVkNjQwXHVjMjE4IFx1YmQ4MFx1YmQ4NFx1YzVmNDogWDxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0ICgxICZsZTsmbmJzcDtUICZsZTsgMTApLjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjY2FiIFx1YzkwNFx1YzVkMCBBXHVjNzU4IFx1YWUzOFx1Yzc3NCBuIFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDAgblx1YWMxY1x1Yzc1OCAwXHVjNzc0XHVjMGMxXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gQVx1Yzc1OCBcdWFjMDEgXHVjNmQwXHVjMThjXHViMjk0IDAgXHVjNzc0XHVjMGMxIDIsMDAwIFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVkNjQwXHVjMjE4IFx1YmQ4MFx1YmQ4NFx1YzVmNFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6Ijx1bD5cclxuXHQ8bGk+XHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCAxOiB7M30sIHszLDZ9LCB7MywgMywgNn0gXHVjMTM4IFx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWQ2NDBcdWMyMTgtXHViZDgwXHViZDg0XHVjNWY0XHVjNzc0IFx1Yzc4OFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCAyOiB7MX0sIHszfSwgezAsMX0sIHswLDN9LCB7MSwyfSwgezIsM30sIHswLDEsMn0sIHswLDIsM30gXHVjNWVjXHViMzVmIFx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWQ2NDBcdWMyMTgtXHViZDgwXHViZDg0XHVjNWY0XHVjNzc0IFx1Yzc4OFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCAzOiBcdWJiMzhcdWM4MWNcdWM1ZDBcdWMxMWMgXHVjMTFjXHVjMjIwXHViNDFjXHViMzAwXHViODVjIFx1YzVlY1x1YjM1ZiBcdWM4ODVcdWI5NThcdWM3NTggXHVkNjQwXHVjMjE4LVx1YmQ4MFx1YmQ4NFx1YzVmNFx1Yzc3NCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCIsInN1YnRhc2sxIjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgbiAmbGU7IDEwPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMiI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IG4gJmxlOyA2MDxcL2xpPlxyXG48XC91bD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMTcyNzkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJPZGQgU3Vic2VxdWVuY2VzIiwiZGVzY3JpcHRpb24iOiI8cD5BIHN1YnNlcXVlbmNlIGlzIGEgc2VxdWVuY2UgdGhhdCBjYW4gYmUgb2J0YWluZWQgZnJvbSBhbiBhcnJheSBieSBkZWxldGluZyAwIG9yIG1vcmUgZWxlbWVudHMuIEZvciBhIHN1YnNlcXVlbmNlIFMgb2YgYW4gYXJyYXkgQSB3aXRoIGxlbmd0aCBuIHRoYXQgY29uc2lzdHMgb2Ygbm9ubmVnYXRpdmUgaW50ZWdlcnMsIHdlIGRlZmluZSBTIGFzIGFuICZxdW90O29kZC1zdWJzZXF1ZW5jZSZxdW90OyBpZiBpdCBzYXRpc2ZpZXMgdGhlIGZvbGxvd2luZyBjb25kaXRpb246PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+U3VtIG9mIGVsZW1lbnRzIG9mIFMgaGFzIGFuIG9kZCBudW1iZXIgb2YgaXRzIGRpZ2l0cy4gVGhlIG51bWJlciBvZiBvZGQgbnVtYmVyKHMpIHNob3VsZCBiZSBvZGQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+R2l2ZW4gYSBub25uZWdhdGl2ZSBpbnRlZ2VyIGFycmF5IEEsIG91dHB1dCB0aGUgbnVtYmVyIG9mIGRpc3RpbmN0IG9kZCBzdWJzZXF1ZW5jZXMgb2YgQS4gVG8gYmUgcHJlY2lzZSwgd2UgdHJlYXQgdHdvIHN1YnNlcXVlbmNlcyBhcyBlcXVpdmFsZW50IGlmIHRoZWlyIHNvcnRlZCByZXN1bHRzIGFyZSBlcXVhbC48XC9wPlxyXG5cclxuPHA+Rm9yIGluc3RhbmNlLCBzdXBwb3NlIEEgPSBbIDMsIDMsIDYsIDgsIDYgXS4mbmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5PZGQgc3Vic2VxdWVuY2VzIG9mIEEgd2l0aCBsZW5ndGggMCA6IC08XC9saT5cclxuXHQ8bGk+T2RkIHN1YnNlcXVlbmNlcyBvZiBBIHdpdGggbGVuZ3RoIDEgOiBbM11cclxuXHQ8dWw+XHJcblx0XHQ8bGk+VGhlIHN1bSBvZiBlbGVtZW50cyBpcyAzLCB3aGljaCBoYXMgYSBzaW5nbGUgb2RkIGRpZ2l0IDM8XC9saT5cclxuXHQ8XC91bD5cclxuXHQ8XC9saT5cclxuXHQ8bGk+T2RkIHN1YnNlcXVlbmNlcyBvZiBBIHdpdGggbGVuZ3RoIDIgOiBbMywgNl0sIFs2LCA2XSwgWzYsIDhdXHJcblx0PHVsPlxyXG5cdFx0PGxpPlRoZSBzdW1zIG9mIGVsZW1lbnRzIGFyZSA5LCAxMiwgMTQgcmVzcGVjdGl2ZWx5LCB3aXRoIHNpbmdsZSBvZGQgZGlnaXQgOSwgMSwgMTxcL2xpPlxyXG5cdDxcL3VsPlxyXG5cdDxcL2xpPlxyXG5cdDxsaT5PZGQgc3Vic2VxdWVuY2VzIG9mIEEgd2l0aCBsZW5ndGggMyA6IFszLCAzLCA2XSwgWzMsIDMsIDhdPFwvbGk+XHJcblx0PGxpPk9kZCBzdWJzZXF1ZW5jZXMgb2YgQSB3aXRoIGxlbmd0aCA0IDogWzMsIDMsIDYsIDZdLCBbMywgNiwgNiwgOF08XC9saT5cclxuXHQ8bGk+T2RkIHN1YnNlcXVlbmNlcyBvZiBBIHdpdGggbGVuZ3RoIDUgOiAtPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIHdpbGwgY29udGFpbiBhbiBpbnRlZ2VyIFQgKDEgJmxlOyZuYnNwO1QgJmxlOyZuYnNwOzEwKSwgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLjxcL3A+XHJcblxyXG48cD5Gb3IgZWFjaCB0ZXN0IGNhc2U6IFRoZSBmaXJzdCBsaW5lIHdpbGwgY29udGFpbiBuLCBhbmQgdGhlIHNlY29uZCBsaW5lIHdpbGwgY29udGFpbiBuIG5vbi1uZWdhdGl2ZSBpbnRlZ2VycyBkZXNjcmliaW5nIEEuIEVhY2ggZWxlbWVudCBvZiBBIHdpbGwgYmUgYmV0d2VlbiAwIGFuZCAyLDAwMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBpbiBhIHNsaW5nZSBsaW5lIHRoZSBudW1iZXIgb2Ygb2RkIHN1YnNlcXVlbmNlcyB5b3UgY2FuIG1ha2Ugb3V0IG9mIEEuPFwvcD5cclxuIiwiaGludCI6Ijx1bD5cclxuXHQ8bGk+VGVzdCBjYXNlIDE6IHszfSwgezMsNn0sIGFuZCB7MywgMywgNn0gYXJlIHRoZSBvbmx5IHRocmVlIG9kZCBzdWJzZXF1ZW5jZXMmbmJzcDtvZiBBLjxcL2xpPlxyXG5cdDxsaT5UZXN0IGNhc2UgMjogezF9LCB7M30sIHswLDF9LCB7MCwzfSwgezEsMn0sIHsyLDN9LCB7MCwxLDJ9LCBhbmQgezAsMiwzfSBhcmUgdGhlIG9kZCBzdWJzZXF1ZW5jZXMgb2YgQS48XC9saT5cclxuXHQ8bGk+VGVzdCBjYXNlIDM6IDggb2RkIHMgb2YgQSB3ZXJlIGRlc2NyaWJlZCBpbiB0aGUgcHJvYmxlbSBzdGF0ZW1lbnQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCIsInN1YnRhc2sxIjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgbiAmbGU7IDEwPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMiI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IG4gJmxlOyA2MDxcL2xpPlxyXG48XC91bD5cclxuIn1d

채점

  • 예제는 채점하지 않는다.