제3회 IUPC

IUPC(International University student Product Contest)는 세 명이 한 팀을 이뤄 큰 수의 곱셈을 얼마나 빠르고 정확하게 계산하는지 겨루는 대회다. 제1회 대상은 인하대학교의 "I inha U" 팀이, 제2회 대상도 인하대학교의 "URF" 팀이 차지했다. 그리고 오늘, 제3회 IUPC가 열린다.

즐거운 날이지만 참가 팀의 마음은 편하지 않다. 대회를 주관하는 CTP가 매번 인하대학교만 대상을 타면 다른 대학 팀의 사기가 떨어진다고 보고 규칙을 바꿨기 때문이다.

예전 대회는 큰 수 두 개를 주고 빠르게 곱하기만 하면 되는 단순한 대회였다. 제3회 IUPC는 다음 순서로 진행된다.

1. $N$개의 줄에 걸쳐 $A$, $B$, $C$가 차례대로 주어진다.
2. $i$번째 줄에 주어진 값을 $A_i$, $B_i$, $C_i$라고 하자. 모든 $i$에 대해 $A_i \times B_i^0$, $A_i \times B_i^1$, $A_i \times B_i^2$, $\dots$, $A_i \times B_i^{C_i}$를 계산하고 각 결과를 카드 한 장에 하나씩 적는다.
3. 계산을 모두 마치면 카드가 $\sum_{i=1}^{N}{(C_i+1)}$장 생긴다. 적힌 수가 같은 카드끼리 한 묶음으로 모은다.
4. 이렇게 정리하면 묶음이 $K$개 생긴다. $K$는 카드 수와 같을 수도 있고 그보다 작을 수도 있다. $K$를 가장 빠르게 계산하는 팀이 우승한다.

첫 번째 줄에 $N$($1 \le N \le 100$)이 주어진다. 두 번째 줄부터 $N$개의 줄에 걸쳐 $A_i$, $B_i$, $C_i$가 공백으로 구분되어 주어진다. ($2 \le A_i, B_i \le 100{,}000$, $1 \le C_i \le 100{,}000$)

첫 번째 줄에 규칙대로 카드를 정리했을 때 생기는 묶음의 수 $K$를 출력한다.