There are n criminals in the city. According to the rules, each criminal should have a unique id number of form "xxx-yyy" where xxx is a 3-number id of the gang and yyy is a 3-number id of the criminal inside the gang. Moreover, in a valid id number, yyy is always a permutation of xxx, i.e., xxx can be converted into yyy by reordering the numbers. For example, valid id numbers include 176-716 and 311-131.

Given a list of id numbers, your first task is to check that each criminal has a unique valid id number. After this, calculate how many gangs exist in the city.

Input

The first input line contains an integer n: the number of criminals. After this, n lines follow. Each line contains an id number of form "xxx-yyy".

Output

If the list is not consistent (id numbers are not unique or valid), output QAQ. Otherwise, output the number of criminal gangs.

Constraints

• 1 \le n \le 1000

Example

Input:

5
176-671
176-617
176-716
176-167
176-176

Output:

1

Input:

3
123-321
123-312
312-123

Output:

2

Input:

2
123-123
123-123

Output:

QAQ

Input:

2
123-123
123-456

Output:

QAQ