Problem Description
Clarke is a patient with multiple personality disorder. One day, Clarke turned into a game player of minecraft.
On that day, Clarke set up local network and chose create mode for sharing his achievements with others. Unfortunately, a naughty kid came his game. He placed a few creepers in Clarke's castle! When Clarke returned his castle without create mode, creepers suddenly blew(what a amazing scene!). Then Clarke's castle in ruins, the materials scattered over the ground.
Clark had no choice but to pick up these ruins, ready to rebuild. After Clarke built some chests(boxes), He had to pick up the material and stored them in the chests. Clarke clearly remembered the type and number of each item(each item was made of only one type material) . Now Clarke want to know how many times he have to transport at least.
Note: Materials which has same type can be stacked, a grid can store materials of same type at most. Different types of materials can be transported together. Clarke's bag has 4*9=36 grids.
Input
The first line contains a number T(≤T≤), the number of test cases.
For each test case:
The first line contains a number n, the number of items.
Then n lines follow, each line contains two integer a,b(≤a,b≤), a denotes the type of material of this item, b denotes the number of this material.
Output
For each testcase, print a number, the number of times that Clarke need to transport at least.
Sample Input
Sample Output
Hint:
The first sample, we need to use grids to store the materials of type and grid to store the materials of type . So we only need to transport once;
Source
附上中文题目：
克拉克是一名人格分裂患者。某一天，克拉克分裂成了一个学生，在做题。
突然一道难题难到了克拉克，这道题是这样的：
给你n个数，要求选一些数（可以不选），把它们加起来，使得和恰好是p的倍数（0也是p的倍数），求方案数。
对于n很小的时候，克拉克是能轻易找到的。然而对于n很大的时候，克拉克没有办法了，所以来求助于你。
附上官方题解：
贪心，将同样材料堆到一格里，然后每一次都装满36个格子，装满就运即可。注意取上界操作。
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<bitset>
#include<map>
#include<vector>
#include<stdlib.h>
#include <stack>
using namespace std;
int dirx[]={,,-,};
int diry[]={-,,,};
#define PI acos(-1.0)
#define max(a,b) (a) > (b) ? (a) : (b)
#define min(a,b) (a) < (b) ? (a) : (b)
#define ll long long
#define eps 1e-10
#define MOD 1000000007
#define N 1000000
#define inf 1e12
int n;
map<int,int>mp; int main()
{
int t;
scanf("%d",&t);
while(t--){
mp.clear();
scanf("%d",&n);
for(int i=;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
mp[x]+=y;
} int ans=;
int g=;
for(int i=;i<=;i++){
if(mp[i]){
g+=mp[i]/;
if(mp[i]%!=){
g++;
}
}
} ans=ans+g/; if(g%!=){
ans++;
}
printf("%d\n",ans); }
return ;
}