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

문제

해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 몇 일동안 밖에 돌아다닐 수 있을까?

입력

첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다.

  • 각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다.
  • 다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 같은 종류의 의상은 하나만 입을 수 있다.

모든 문자열은 1이상 20이하의 알파벳 소문자로 이루어져있으며 같은 이름을 가진 의상은 존재하지 않는다.

출력

각 테스트 케이스에 대해 해빈이가 알몸이 아닌 상태로 의상을 입을 수 있는 경우를 출력하시오.

예제 입력 1

2
3
hat headgear
sunglasses eyewear
turban headgear
3
mask face
sunglasses face
makeup face

예제 출력 1

5
3

힌트

첫번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로   (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다.

W3sicHJvYmxlbV9pZCI6IjkzNzUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMjhcdWMxNThcdWM2NTUgXHVjMmUwXHVkNTc0XHViZTQ4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1NzRcdWJlNDhcdWM3NzRcdWIyOTQgXHVkMzI4XHVjMTU4XHVjNWQwIFx1YjllNFx1YzZiMCBcdWJiZmNcdWFjMTBcdWQ1NzRcdWMxMWMgXHVkNTVjXHViYzg4IFx1Yzc4NVx1YzVjOFx1YjM1OCBcdWM2MzdcdWI0ZTRcdWM3NTggXHVjODcwXHVkNTY5XHVjNzQ0IFx1YzgwOFx1YjMwMCBcdWIyZTRcdWMyZGMgXHVjNzg1XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBcdWM2MjRcdWIyOTggXHVkNTc0XHViZTQ4XHVjNzc0XHVhYzAwIFx1YzU0OFx1YWNiZCwgXHVjZjU0XHVkMmI4LCBcdWMwYzFcdWM3NTgsIFx1YzJlMFx1YmMxY1x1Yzc0NCBcdWM3ODVcdWM1YzhcdWIyZTRcdWJhNzQsIFx1YjJlNFx1Yzc0Y1x1YjBhMFx1Yzc0MCBcdWJjMTRcdWM5YzBcdWI5N2MgXHVjZDk0XHVhYzAwXHViODVjIFx1Yzc4NVx1YWM3MFx1YjA5OCBcdWM1NDhcdWFjYmRcdWIzMDBcdWMyZTAgXHViODBjXHVjOTg4XHViOTdjIFx1Y2MyOVx1YzZhOVx1ZDU1OFx1YWM3MFx1YjA5OCBcdWQ1NzRcdWM1N2NcdWQ1NWNcdWIyZTQuIFx1ZDU3NFx1YmU0OFx1Yzc3NFx1YWMwMCBcdWFjMDBcdWM5YzQgXHVjNzU4XHVjMGMxXHViNGU0XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NFx1YjU0YyBcdWFjZmNcdWM1ZjAgXHVkNTc0XHViZTQ4XHVjNzc0XHViMjk0IFx1YzU0Y1x1YmFiOFx1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjMGMxXHVkMGRjXHViODVjIFx1YmE4NyBcdWM3N2NcdWIzZDlcdWM1NDggXHViYzE2XHVjNWQwIFx1YjNjY1x1YzU0NFx1YjJlNFx1YjJkMCBcdWMyMTggXHVjNzg4XHVjNzQ0XHVhZTRjPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWNkNWNcdWIzMDAgMTAwXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNTc0XHViZTQ4XHVjNzc0XHVhYzAwIFx1YWMwMFx1YzljNCBcdWM3NThcdWMwYzFcdWM3NTggXHVjMjE4IG4oMCAmbGU7IG4gJmxlOyAzMClcdWM3NzQmbmJzcDtcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YjJlNFx1Yzc0YyBuXHVhYzFjXHVjNWQwXHViMjk0IFx1ZDU3NFx1YmU0OFx1Yzc3NFx1YWMwMCBcdWFjMDBcdWM5YzQmbmJzcDtcdWM3NThcdWMwYzFcdWM3NTggXHVjNzc0XHViOTg0XHVhY2ZjIFx1Yzc1OFx1YzBjMVx1Yzc1OCBcdWM4ODVcdWI5NThcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMxOVx1Yzc0MCBcdWM4ODVcdWI5NThcdWM3NTggXHVjNzU4XHVjMGMxXHVjNzQwIFx1ZDU1OFx1YjA5OFx1YjljYyBcdWM3ODVcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIDFcdWM3NzRcdWMwYzEgMjBcdWM3NzRcdWQ1NThcdWM3NTggXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzhcdWM3ODhcdWM3M2NcdWJhNzAgXHVhYzE5XHVjNzQwIFx1Yzc3NFx1Yjk4NFx1Yzc0NCBcdWFjMDBcdWM5YzQgXHVjNzU4XHVjMGMxXHVjNzQwIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1ZDU3NFx1YmU0OFx1Yzc3NFx1YWMwMCBcdWM1NGNcdWJhYjhcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzBjMVx1ZDBkY1x1Yjg1YyBcdWM3NThcdWMwYzFcdWM3NDQgXHVjNzg1XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjY2FiXHViYzg4XHVjOWY4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgaGVhZGdlYXJcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1Yzc1OFx1YzBjMVx1Yzc3NCBoYXQsIHR1cmJhblx1Yzc3NFx1YmE3MCBleWV3ZWFyXHVjNWQwIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWM3NThcdWMwYzFcdWM3NzQgc3VuZ2xhc3Nlc1x1Yzc3NFx1YmJjMFx1Yjg1YyAmbmJzcDsgKGhhdCksICh0dXJiYW4pLCAoc3VuZ2xhc3NlcyksIChoYXQsc3VuZ2xhc3NlcyksICh0dXJiYW4sc3VuZ2xhc3NlcylcdWI4NWMgXHVjZDFkIDVcdWFjMDBcdWM5YzAgXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTM3NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkluY29nbml0byIsImRlc2NyaXB0aW9uIjoiPHA+U3BpZXMgdXNlIGF0dHJpYnV0ZXMgdG8gZGlzZ3Vpc2UgdGhlbXNlbHZlcyB0byBtYWtlIHN1cmUgdGhhdCB0aGV5IGFyZSBub3QgcmVjb2duaXplZC4gRm9yIGV4YW1wbGUsIHdoZW4gcHV0dGluZyBvbiBzdW5nbGFzc2VzLCBhIHNweSBzdWRkZW5seSBsb29rcyBjb21wbGV0ZWx5IGRpZmZlcmVudCBhbmQgY2Fubm90IGJlIHJlY29nbml6ZWQgYW55bW9yZS4gRXZlcnkgY29tYmluYXRpb24gb2YgYXR0cmlidXRlcyBnaXZlcyBhIGRpZmZlcmVudCBhcHBlYXJhbmNlLCBidXQgbm90IGFsbCBjb21iaW5hdGlvbnMgYXJlIHBvc3NpYmxlLiBGb3IgZXhhbXBsZSwgYSBoYXQgYW5kIGEgdHVyYmFuIGFyZSBib3RoIGhlYWRnZWFyIGFuZCBjYW5ub3QgYmUgdXNlZCBhdCB0aGUgc2FtZSB0aW1lLiBHaXZlbiB0aGUgbGlzdCBvZiBhdmFpbGFibGUgYXR0cmlidXRlcywgY29tcHV0ZSBob3cgbWFueSBkaXN0aW5jdCBkaXNndWlzZXMgY2FuIGJlIG1hZGUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgXHVmYjAxcnN0IGxpbmUgb25lIHBvc2l0aXZlIG51bWJlcjogdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLCBhdCBtb3N0IDEwMC4gQWZ0ZXIgdGhhdCBwZXIgdGVzdCBjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggYW4gaW50ZWdlciBuICgwICZsZTsgbiAmbGU7IDMwKTogdGhlIG51bWJlciBvZiBhdmFpbGFibGUgYXR0cmlidXRlcy48XC9saT5cclxuXHQ8bGk+biBsaW5lcyB3aXRoIHR3byBzcGFjZS1zZXBhcmF0ZWQgc3RyaW5nczogdGhlIG5hbWUgYW5kIHRoZSBjYXRlZ29yeSBvZiB0aGUgYXR0cmlidXRlLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkFsbCBzdHJpbmdzIGNvbnNpc3Qgb2YgYXQgbGVhc3QgMSBhbmQgYXQgbW9zdCAyMCBsb3dlcmNhc2UgbGV0dGVycy4gV2l0aGluIGEgdGVzdCBjYXNlIGFsbCBuYW1lcyBhcmUgZGlzdGluY3QuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIGFuIGludGVnZXI6IHRoZSBudW1iZXIgb2YgcG9zc2libGUgZGlzdGluY3QgZGlzZ3Vpc2VzIHRoYXQgY2FuIGJlIG1hZGUgd2l0aCB0aGUgZ2l2ZW4gYXR0cmlidXRlcywgc3VjaCB0aGF0IGF0IG1vc3Qgb25lIGF0dHJpYnV0ZSBmcm9tIGVhY2ggY2F0ZWdvcnkgaXMgdXNlZC48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==